Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。今天早上，如同往常一样，Farmer John 的N 头编号为 1…N 的奶牛（1≤N≤10$^5$），分散在牛棚中N 个编号为1…N 的不同位置，奶牛 i 位于位置 p$_i$。但是今天早上还出现了 M 个编号为 1…M 的虫洞（1≤M≤10$^5$），其中虫洞 i 双向连接了位置 a$_i$ 和 b$_i$，宽度为 w$_i$（1≤a$_i$,b$_i$≤N,a$_i$≠b$_i$,1≤w$_i$≤10$^9$）。

在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 1≤i≤N，奶牛 i 位于位置i。

奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。

测试点性质：

• 测试点 3-5 满足 N,M≤1000。
• 测试点 6-10 没有额外限制。

输入格式（文件名：wormsort.in）：

输入的第一行包含两个整数N 和 M。第二行包含 N 个整数 p$_1$,p$_2$,…,p$_N$。保证p 是 1…N 的一个排列。

对于 1 到M 之间的每一个 i，第 i+2 行包含整数 a$_i$、b$_i$ 和 w$_i$。

输出格式（文件名：wormsort.out）：

输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 −1。

输入样例：

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

输出样例：

9

以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案：

• 奶牛 1 和奶牛 2 使用第三个虫洞交换位置。
• 奶牛 1 和奶牛 3 使用第一个虫洞交换位置。
• 奶牛 2 和奶牛 3 使用第三个虫洞交换位置。

输入样例：

4 1
1 2 3 4
4 2 13

输出样例：

-1

给奶牛们排序不需要使用任何虫洞。