웜홀 정렬

Farmer John의 소들은 매일 아침 헛간을 떠나기 전에 스스로 줄을 정렬하라는 요청에 지쳤다. 소들은 방금 양자물리학 박사 학위를 받았고, 이 일을 좀 더 빠르게 처리할 준비가 되어 있다.

오늘 아침에도 여느 때처럼 Farmer John의 $N$마리 소($1 \leq N \leq 10^5$)가 $1 \dots N$으로 번호가 붙은 헛간의 $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\neq b\_i, 1\le w\_i\le 10^9$).

언제든지 웜홀의 양 끝에 있는 두 소는 웜홀을 통해 동시에 자리를 바꿀 수 있다. 소들은 $1 \leq i \leq N$에 대해 소 $i$가 위치 $i$에 올 때까지 이런 교환을 수행해야 한다.

소들은 웜홀에 눌려 납작해지고 싶지 않다. 소들이 정렬을 마치기 위해 반드시 사용해야 하는 웜홀 중 가장 좁은 웜홀의 폭을 최대화하도록 도와주자. 소들이 스스로 정렬할 수 있음은 보장된다.

첫째 줄에 정수 $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$을 출력한다.