ykw 的西瓜计划
说明
夏天到了！作为 wjy 优秀的好朋友，ykw 决定去西瓜地里给 wjy 摘一些西瓜吃
聪明的 ykw 提前用无人机观察过整个瓜地，他总共找出了 $n$ 个他摘的到的西瓜地，按照大小分别编号为 $1$ 到 $n$
同时，他已经提前规划好了 $m$ 条小路
第 $i$ 条小路可以从 $x_i$ 号西瓜地走向 $y_i$ 号西瓜地，长度为 $len_i$，但是因为瓜地非常难走，所以 $y_i$ 号西瓜地不能通过这条小路走向 $x_i$ 号西瓜地
$1$ 号西瓜地在路边，ykw 很容易就可以摘到它的西瓜，但是 $1$ 号西瓜地的西瓜是最小的， pxb 想给 wjy 最好的西瓜，于是他决定去摘 $n$ 号西瓜地的西瓜！
而 ykw 很贪心，如果他经过了一个西瓜地，他就一定会摘一个这个西瓜地的西瓜，但是显然背的西瓜越多，走路就越累
这里我们认为每个西瓜地有足够多的西瓜供 ykw 去摘，重复经过一个西瓜地也会重复摘西瓜
如果 ykw 现在要带着 $now$ 颗西瓜穿过一条长度为 $len$ 的小路，那么他会增加 $now * len$ 点疲劳度
现在 ykw 想知道，怎么走可以使得自己以最小的疲劳度摘到第 $n$ 号西瓜？
输入格式
第一行两个整数表示 $n$ 和 $m$
接下来 $m$ 行每行三个整数 $x_i,y_i,len_i$ ，表示有一条长度为 $len_i$ 的小路可以从 $x_i$ 走向 $y_i$
对于 $30\%$ 的数据，$n \leq 100$
对于另外 $20\%$ 的数据， $m=n-1$
对于 $100\%$ 的数据，$n \leq 1000,m \leq 20000,len_i \leq 10^6$
题目保证不会出现环
输出格式
输出 ykw 摘到第 $n$ 号西瓜的最小疲劳度
样例
4 6
1 3 2
1 2 1
2 3 2
3 4 1
2 4 2
1 4 54提示
走 $1-3$ 花费为 $1 * 2 = 2$
再走 $3-4$ 花费为 $2 * 1 = 2$
最小花费为 $2 + 2 = 4$
相关
在下列比赛中: