Wormhole Sort

문제

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 $NN$ cows ($1\le N\le {10}^{5}1\; \backslash leq\; N\; \backslash leq\; 10^5$), conveniently numbered $1\dots N1\; \backslash dots\; N$, are scattered throughout the barn at $NN$ distinct locations, also numbered $1\dots N1\; \backslash dots\; N$, such that cow $ii$ is at location $p_{i}p\_i$. But this morning there are also $MM$ wormholes ($1\le M\le {10}^{5}1\; \backslash leq\; M\; \backslash leq\; 10^5$), numbered $1\dots M1\; \backslash dots\; M$, where wormhole $ii$ bidirectionally connects location $a_{i}a\_i$ with location $b_{i}b\_i$, and has a width $w_{i}w\_i$ ($1\le a_i,b_i\le N,a_i\mathrm{\ne }{b}_i,1\le w_i\le {10}^{9}1\backslash le\; a\_i,b\_i\backslash le\; N,\; a\_i\backslash neq\; b\_i,\; 1\backslash le\; w\_i\backslash le\; 10^9$).

At any point in time, two cows located at opposite ends of a wormhole may choose to simultaneously swap places through the wormhole. The cows must perform such swaps until cow $ii$ is at location $ii$ for $1\le i\le N1\; \backslash leq\; i\; \backslash leq\; N$.

The cows are not eager to get squished by the wormholes. Help them maximize the width of the least wide wormhole which they must use to sort themselves. It is guaranteed that it is possible for the cows to sort themselves.

입력

The first line contains two integers, $NN$ and $MM$.

The second line contains the $NN$ integers $p_1,p_2,\dots ,p_{N}p\_1,\; p\_2,\; \backslash dots,\; p\_N$. It is guaranteed that $pp$ is a permutation of $1\dots N\mathrm{.}1\backslash ldots\; N.$

For each $ii$ between $11$ and $MM$, line $i+2i+2$ contains the integers $a_{i}a\_i$, $b_{i}b\_i$, and $w_{i}w\_i$.

출력

A single integer: the maximum minimal wormhole width which a cow must squish itself into during the sorting process. If the cows do not need any wormholes to sort themselves, output $-1-1$.

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

9

4 1
1 2 3 4
4 2 13

-1