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

第一行两个整数表示 $n$ 和 $m。$
接下来 $m$ 行每行三个整数 ui,vi,wiu_i,v_i,w_iui,v_i,w_i ，分别表示这条边的起点终点和距离。

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