该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

fw香蕉猫又在哭了，让我们来帮帮它解决问题吧。

在猫星球，有 $N$ 处地点藏着美味的猫条，但是这 $N$ 个地点是不连通的，我们无法从一处到另一处。香蕉猫想要吃到这 $N$ 处地点的所有猫条，总所周知，fw香蕉猫就只会哭哭哭，我们会通过一些手段让他哭 $M$ 次，每一次哭都可以在两处地点哭出一条水路，使得两点双向联通，我们需要求出在最早的时刻，香蕉猫可以不用再哭便能吃遍这 $N$ 个地点的所有猫条。

描述

给出 $N$，$M$，代表有 $N$ 处地点，随后 $M$ 条记录里每行 $3$ 个正整数 $x,y,t$，代表 $t$ 时刻香蕉猫哭出了 $x$ 与 $y$ 之间的双向水路。求解最早在什么时候实现“猫条自由”。（使得 $N$ 个点相互联通）

格式

输入

第 1 行两个正整数 $N,M$。下面 $M$ 行，每行 3 个正整数 $x , y , t$，在时间 $t$ 时能建成 $x 和 y$ 之间的这条水路。

$1 \le x , y \le N \le 10^5; 1 \le M \le 10^5 ; 1 \le t \le 10^9$。

输出

如果哭完 $M$ 次，仍然存在两个地点无法联通，则输出 -1 ，否则输出最早什么时候任意两个地点能够联通。

样例

5 6
1 3 1
4 5 10
1 5 8
2 3 6
2 5 4
3 5 13

10