401 - 最短路

通过次数

98

提交次数

237

时间限制 : 1 秒
内存限制 : 128 MB

wlxsq有一个图G,由n个点,m条边构成,点的编号从1n,每条边有一个花费c

求从点1到点n的最小花费。

注意:有重边,无向图

输入

第一行输入两个整nm,表示点数和边数( n <= 1000, m <= 10000)。

接下来m行,每行包含3个整数a,b,c,表示有一条ab相连,花费为c的边。

输出

输出一行,表示从点1到点n的最短路

样例

输入

3 3
1 2 5
2 3 5
3 1 2

输出

2