题目描述

夏天到了！

作为 ztm 优秀的好朋友，mhl 决定去西瓜地里给 ztm 摘一些西瓜吃

聪明的 mhl 提前用无人机观察过整个瓜地，他总共找出了 $n$ 个他摘的到的西瓜地，按照大小分别编号为 $1$ 到 $n$

同时，他已经提前规划好了 $m$ 条小路

第 $i$ 条小路可以从 $x_i$ 号西瓜地走向 $y_i$ 号西瓜地，长度为 $len_i$，但是因为瓜地非常难走，所以 $y_i$ 号西瓜地不能通过这条小路走向 $x_i$ 号西瓜地

$1$ 号西瓜地在路边，mhl 很容易就可以摘到它的西瓜，但是 $1$ 号西瓜地的西瓜是最小的， mhl 想给 ztm 最好的西瓜，于是他决定去摘 $n$ 号西瓜地的西瓜！

而 mhl 很贪心，如果他经过了一个西瓜地，他就一定会摘一个这个西瓜地的西瓜，但是显然背的西瓜越多，走路就越累

这里我们认为每个西瓜地有足够多的西瓜供 mhl 去摘，重复经过一个西瓜地也会重复摘西瓜

如果 mhl 现在要带着 $now$ 颗西瓜穿过一条长度为 $len$ 的小路，那么他会增加 $now * len$ 点疲劳度

现在 mhl 想知道，怎么走可以使得自己以最小的疲劳度摘到第 $n$ 号西瓜？

输入格式

第一行两个整数表示 $n$ 和 $m$

接下来 $m$ 行每行三个整数 $x_i,y_i,len_i$ ，表示有一条长度为 $len_i$ 的小路可以从 $x_i$ 走向 $y_i$

输出格式

输出 mhl 摘到第 $n$ 号西瓜的最小疲劳度

数据范围

对于 $30\%$ 的数据，$n \leq 100$

对于另外 $20\%$ 的数据， $m=n-1$

对于 $100\%$ 的数据，$n \leq 1000,m \leq 20000,len_i \leq 10^6$

样例输入

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

样例输出

4

样例解释

走 $1-3$ 花费为 $1 * 2 = 2$ 再走 $3-4$ 花费为 $2 * 1 = 2$ 最小花费为 $2 + 2 = 4$