웜홀 정렬

현주의 $N$마리의 강아지들($1 \leq N \leq 10^5$)이 편리하게 $1 \dots N$의 번호가 매겨져 집 안 어딘가에 흩어져 있습니다. 각각의 위치에도 $1 \dots N$의 번호가 매겨져 있어서 "강아지 $i$는 위치 $p_i$에 있습니다."라고 표현할 수 있습니다. 

또한 $M$ 개의 웜홀 ($1 \leq M \leq 10^5$)이 있으며, 웜홀도 $1 \dots M$의 번호가 매겨져 있습니다. 여기서 웜홀 $i$는 위치 $a_i$와 위치 $b_i$를 양방향으로 연결하며, 폭이 $w_i$입니다 ($1 \le a_i,b_i \le N, a_i eq b_i, 1 \le w_i \le 10^9$).

두 강아지가 웜홀의 양끝에 위치해서 동시에 웜홀을 통해 위치를 바꿀 수 있습니다. 강아지들은 강아지 $i$가 $1 \leq i \leq N$의 위치에 있을 때까지 이러한 교환이 계속 이루어져야 합니다.

강아지들은 웜홀로 들어갈 기미가 보이지 않습니다. 강아지들이 스스로 정렬하는 데 사용해야 하는 최소 너비의 웜홀의 너비를 최대화하도록 도와주세요. 

강아지들이 스스로 정렬하는 것이 가능하다는 것이 보장됩니다.

첫 번째 줄에는 두 개의 정수, $N$과 $M$이 포함되어 있습니다.

두 번째 줄에는 $N$개의 정수 $p_1, p_2, \dots, p_N$이 포함되어 있습니다. $p$는 $1 \ldots N.$의 순열임이 보장됩니다.

1부터 $M$까지의 $i$에 대해, $i+2$번째 줄에는 정수 $a_i$, $b_i$, 그리고 $w_i$가 포함되어 있습니다.

하나의 정수 : 강아지가 정렬 과정 중 최소한으로 웜홀의 폭을 최대화합니다. 

강아지들이 자신들을 정렬하는 데 웜홀이 필요하지 않은 경우, $-1$을 출력합니다.