Problem Description

Farmer John's cows are tired of his requirement for them to line up in order every morning. They've just completed their PhDs in quantum physics and are ready to speed up the process.

As usual, Farmer John's $N$ cows (numbered $1 \ldots N$, where $1 \leq N \leq 10^5$) are scattered in the barn at $N$ distinct positions numbered $1 \ldots N$, with cow $i$ at position $p_i$. However, today also features $M$ wormholes (numbered $1 \ldots M$, where $1 \leq M \leq 10^5$), where wormhole $i$ connects positions $a_i$ and $b_i$ bidirectionally with a width of $w_i$ ($1 \leq a_i, b_i \leq N, a_i \neq b_i, 1 \leq w_i \leq 10^9$).

At any time, two cows at opposite ends of a wormhole can choose to swap positions through the wormhole. The cows need to repeatedly perform such swaps until, for $1 \leq i \leq N$, cow $i$ is at position $i$.

The cows do not want to be squeezed by the wormholes. Help them maximize the minimum width of the wormholes they must use for sorting. It is guaranteed that the cows can sort themselves.

Input Format

The first line of input 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$, the $(i+2)$-th line contains integers $a_i, b_i, w_i$.

Output Format

Output a single integer, which is the maximum of the minimum width of the wormholes that the cows must squeeze through during the sorting process. If the cows do not need to use any wormholes to sort, output $-1$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

9

Input Sample #2

4 1
1 2 3 4
4 2 13

Output Sample #2

-1

Notes

Sample Explanation 1

Here is a possible way to sort the cows using only wormholes with a width of at least 9:

• Cow 1 and Cow 2 swap using the third wormhole.
• Cow 1 and Cow 3 swap using the first wormhole.
• Cow 2 and Cow 3 swap using the third wormhole.

Subtasks

• Test cases $3 \sim 5$ satisfy $N, M \leq 1000$.
• Test cases $6 \sim 10$ have no additional constraints.

见题面 Input 部分

见题面 Output 部分