Quantum Cow Sorting

Farmer John's cows have had enough of being forced to line up in the barn every morning. Now armed with Ph.D.s in quantum physics, they plan to speed up the process, but without getting squeezed by the wormholes they use for swapping positions!

This morning there are N cows (numbered 1 to N) occupying N distinct positions (also numbered 1 to N). Cow i is initially at position p_i. In addition, there are M wormholes (numbered 1 to M). Wormhole i connects positions a_i and b_i bidirectionally, and its width is given by \(w_i\) (with \(1 \le a_i,b_i \le N,\ a_i\ne b_i,\) and \(1 \le w_i \le 10^9\)).

At any moment, two cows that are positioned at the two ends of a wormhole can swap positions through it. The cows may perform such swaps repeatedly until cow i is at position i for every \(1 \le i \le N\). Since the cows don’t want to be squished, they wish to maximize the minimum width among all the wormholes that are used in the sorting process.

If the cows are already in sorted order (i.e. cow i is at position i for every \(i\)), output -1. Otherwise, find the maximum value \(X\) such that if only wormholes of width at least \(X\) are available, the cows can rearrange themselves into sorted order.

It is guaranteed that the cows can be sorted (if swaps are needed).

inputFormat

The first line contains two space-separated integers \(N\) and \(M\) (\(1 \le N, M \le 10^5\)).

The next line contains \(N\) integers \(p_1, p_2, \ldots, p_N\) representing the initial positions of the cows.

Each of the following \(M\) lines contains three space-separated integers \(a_i\), \(b_i\), and \(w_i\), indicating that there is a wormhole connecting positions \(a_i\) and \(b_i\) with width \(w_i\).

outputFormat

Output a single integer, the maximum possible value of the minimum wormhole width which must be used during the sorting process. If the cows are already sorted, print -1.

sample

4 3
2 3 4 1
1 2 5
2 3 4
3 4 3

3