题目描述Description

给你一个无向图，问从起点 1 出发到达终点 n 的最短路是多少？若不存在从 1 到 n 的路径，输出 -1。

注意：这里的代价不是路径中所有权值之和，而是路径中所有边权值的最大值。

输入格式Input

第一行包含两个整数 n, m，表示结点数和边数。

接下来 m 行，每行 3 个整数：x y z，分别表示有一条边权为 z 的边连接了 x，y。

输出格式Output

输出一个整数表示答案。

样例Sample

提示Hint

数据范围: 1\le n,\ m\le10^6， 1\le x,y\le n， 1\le z\le 10^9

来源Source