1492 : 奇怪的最短路

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
0 次Times
通过次数Solved
0 次Times

题目描述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