暂无测试数据。

$DD$ 在一张图上旅游，她从 $1$ 号点出发前往 $n$ 号点，图上有 $m$ 条单向边，每条边有起点终点和距离， $DD$ 的体力不大好，她在通过第 $i$ 条边的时候会消耗到 $u_i$ 时已经经过的点数乘上该边的距离，她现在想知道她从 $1$ 号点前往 $n$ 号点最少消耗多少体力

输入格式

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

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$ ，分别表示这条边的起点终点和距离

输出格式

一个整数表示最少花费体力为多少

数据范围

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

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

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

5 6
1 2 1
2 3 2 
1 3 1
2 4 100
3 4 1
4 5 10

33