Wormhole Sort#9601
Farmer John's cows have grown tired of his daily request that they sort themselves before leaving the barn each morning. They have just completed their PhDs in quantum physics and are ready to speed things up a bit.
This morning, as usual, Farmer John's cows, conveniently numbered , are scattered throughout the barn at distinct locations, also numbered , such that cow is at location p_i. However, this morning there are also wormholes, numbered , where wormhole bidirectionally connects locations a_i and b_i and has width w_i.
At any point in time, two cows located at opposite ends of a wormhole may simultaneously swap places through the wormhole. The cows must perform such swaps until cow is at location for every 1 \leq i \leq n.
The cows are not eager to get squished by the wormholes. Help them maximize the minimum width of any wormhole they must use while sorting themselves.
The first line contains two integers n~(1 \le n \le 10^5) and m~(1 \le m \le 10^5).
The second line contains the integers p_1, p_2, \ldots, p_n. It is guaranteed that is a permutation of .
For each between and , line i + 2 contains the integers a_i, b_i, and w_i~(1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le w_i \leq 10^9).
Print one integer: the maximum possible value of the minimum wormhole width among all wormholes used during the sorting process. If the cows do not need to use any wormholes to sort themselves, output .
Here is one possible way to sort the cows using only wormholes of width at least :
Cow and cow swap positions using the third wormhole.
Cow and cow swap positions using the first wormhole.
Cow and cow swap positions using the third wormhole.
Example 1
Example 2