短

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 duan.in 输出文件 duan.out

Problem C. 短

给出无向图G = (V, E),求点V1 和点VN 之间的最短路。

Input Specification

第1行,2个整数|V |和|E|。
第2行到第|E| + 1行,3个整数xi ,yi ,zi ,表示点Vxi 和点Vyi 之间存在权值为wi 的边。

Output Specification

第1行,1个整数,表示最短路的权值。

Input and Output Sample

duan.in
3
1
2
3
3
2 1
3 1
1 1
duan.out
1

Data Restriction

对于50%的数据,N ≤ 1, 000。
对于100%的数据,N ≤ 100, 000, M ≤ 1, 000, 000, 1 ≤ Wi ≤ 2。