题目描述

小婷的牧场中有 $N$ 头奶牛和 $N$ 个位置，奶牛与位置都编号为 $1$ 到 $N$。目前位置 $i$ 上站着奶牛 $p_i$，其中 $p$ 是 $1$ 到 $N$ 的一个排列。小婷希望最终让奶牛 $i$ 回到位置 $i$。

牧场中有 $M$ 条双向虫洞。第 $i$ 条虫洞连接位置 $a_i$ 和位置 $b_i$，宽度为 $w_i$。小婷可以任意多次选择一条虫洞，把虫洞两端位置上的奶牛交换。题目保证存在某种交换方案能够完成排序。

一套交换方案的宽度定义为该方案实际使用过的所有虫洞中最窄的宽度。小婷希望在能够把所有奶牛送回正确位置的前提下，使这套方案的宽度尽可能大。

请输出这个最大宽度。如果所有奶牛一开始就已经位于正确位置，则不需要使用任何虫洞，此时输出 $-1$。

输入格式

第一行输入两个整数 $N,M$。

第二行输入排列 $p_1,p_2,\ldots,p_N$。

接下来 $M$ 行，第 $i$ 行输入三个整数 $a_i,b_i,w_i$，描述第 $i$ 条虫洞。

输出格式

输出完成排序时能够保证的最大虫洞宽度下限；若初始排列已经有序，输出 $-1$。

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

9

样例说明 #1

只使用宽度不小于 $9$ 的虫洞，也能够把奶牛送回正确位置，因此最优答案为 $9$。

4 1
1 2 3 4
4 2 13

-1

样例说明 #2

排列一开始已经有序，不需要使用虫洞，按照规定输出 $-1$。

3 2
2 1 3
1 2 5
2 3 1

5

样例说明 #3

交换位置 $1,2$ 即可完成排序，能够使用的最大宽度下限为 $5$。

数据范围与约定

$1\le N,M\le10^5$，$p$ 是 $1,2,\ldots,N$ 的一个排列，$1\le a_i,b_i\le N$，$a_i\ne b_i$，$1\le w_i\le10^9$。题目保证可以完成排序，输入中的所有数均为整数。