4450 - 第十课:最短路径

给定一个带权无向图。顶点从1到n编号。求从1号点到n号点的最短路径。
 

输入

第一行输入两个整数$ n(2 \le n \le 10^5), m(0 \le m \le 10^5) $。
接下来m行,每行输入三个整数$ a_i, b_i(1 \le a_i, b_i \le n), w_i(1 \le w_i \le 10^6) $,表示$ a_i $和$ b_i $之间有一条长度为$ w_i $的无向边。
 

输出

如果1到n不连通,则输出-1,否则输出最短路径长度。
 

样例

输入

5 4
1 2 2
1 4 1
4 3 3
3 5 1

输出

5
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题