题目描述

农夫约翰的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。

她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。

今天早上，如同往常一样，农夫约翰的 $N$ 头编号为 $1…N$的奶牛，分散在牛棚中 $N$ 个编号为 $1…N$的不同位置，奶牛 $i$位于位置 $p_i$。

但是今天早上还出现了 $M$ 个编号为 $1…M$的虫洞，其中虫洞 $i$双向连接了位置 $a_i$ 和 $b_i$，宽度为 $w_i$。

在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。

奶牛们需要反复进行这样的交换，直到对于 $1≤i≤N$，奶牛$i$位于位置 $i$。

奶牛们不想被虫洞挤坏。

帮助她们最大化被她们用来排序的虫洞宽度的最小值。

保证奶牛们有可能排好序。

输入

输入的第一行包含两个整数 $N$和 $M$。

第二行包含$N$个整数$p_1,p_2,…,p_N$。保证 $p$是 $1…N$的一个排列。

对于 $1$到 $M$之间的每一个 $i$ ，第$i+2$行包含整数$a_i、b_i和 w_i$。

输出

输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。

如果奶牛们不需要用任何虫洞来排序，输出 −1。

样例输入

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

样例输出

9

提示

$1≤N,M≤10^5,$

$1≤a_i,b_i≤N,$

$a_i≠b_i$

$1≤w_i≤10^9$