402 - 最短路(加强版)

通过次数

40

提交次数

135

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

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

注意:有重边,边为有向边

输入

第一行输入两个整nm,表示点数和边数。

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

输出

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

样例

输入

3 3
1 2 5
2 3 5
1 3 2

输出

2

输入

3 3
1 2 5
2 3 5
3 1 2

输出

10

提示

数据规模

对于100\%的数据,1≤n≤50000,1≤m≤200000,1≤a,b≤n,1≤c≤50000