P6004 [USACO20JAN] Wormhole Sort S

Farmer John’s cows are tired of his daily demand that they leave the barn sorted every morning. They have just finished PhDs in quantum physics and are ready to speed this process up. This morning, as usual, Farmer John’s $N$ cows numbered $1 \ldots N$ ($1 \leq N \leq 10^5$) are spread across $N$ distinct positions in the barn, also numbered $1 \ldots N$. Cow $i$ is currently at position $p_i$. However, this morning there are also $M$ wormholes numbered $1 \ldots M$ ($1 \leq M \leq 10^5$). Wormhole $i$ connects positions $a_i$ and $b_i$ in both directions, and has width $w_i$ ($1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9$). At any time, two cows located at the two ends of a wormhole may choose to swap positions through the wormhole. The cows need to repeat such swaps until for all $1 \leq i \leq N$, cow $i$ is at position $i$. The cows do not want to be squeezed by narrow wormholes. Help them maximize the minimum wormhole width among the wormholes they use during the sorting process. It is guaranteed that the cows can be sorted.

The first line contains two integers $N$ and $M$. The second line contains $N$ integers $p_1,p_2,\ldots ,p_N$. It is guaranteed that $p$ is a permutation of $1 \ldots N$. For each $i$ from $1$ to $M$, line $i+2$ contains integers $a_i,b_i,w_i$.

Output one integer: the maximum possible value of the minimum width of any wormhole that the cows must squeeze into during the sorting process. If the cows do not need to use any wormholes to sort, output $-1$.

### Sample Explanation 1 Here is one possible way to sort the cows using only wormholes of width at least $9$: - Cow 1 and cow 2 swap positions using the third wormhole. - Cow 1 and cow 3 swap positions using the first wormhole. - Cow 2 and cow 3 swap positions using the third wormhole. ### Subtasks - Test cases $3 \sim 5$ satisfy $N,M \leq 1000$. - Test cases $6 \sim 10$ have no additional constraints. Translated by ChatGPT 5