Description

PotremZ 是一个死板的人，如今他当起了外卖员，距离自己在当小区门口保安的正轨还有 $30$ 年的光阴需要去浪费。

PotremZ 是一个死板的人，他只为一家店送外卖（难道是XFC炸鸡送？），并且每次只送一份外卖。

PotremZ 所在的城市可以描述为 $n$ 个点 $m$ 条边的​有向图​，PotremZ 将 $1$ 号点标记为自己所打工的店。

现在他有 $n-1$ 份外卖需要送达，每次送达一份外卖后，PotremZ 总会回到店内再去取下一份外卖。

现在 PotremZ 想要知道，自己送完全部外卖，最后回到店内所需要的最少总用时是多少？

Input Format

第一行包括两个整数，$n$ 和 $m$，表示点的数量和边的数量。

第二行到第 $m+1$ 行，每行三个整数 $u,v,w$，表示从 $u$ 点 $v$ 到点 $w$ 有一条耗时为 的道路。

Output Format

输出一行，包含一个整数，为最少总用时。

3 11
1 3 8
2 3 3
1 2 9
2 3 8
2 3 5
2 2 7
2 2 6
3 1 8
2 3 6
3 1 4
3 2 5​

28​

Hint

$1 \le n \le 10^3$,

$1 \le m \le 10^5$,

$1 \le u,v \le n$,

$1 \le w \le 10^4$,

数据保证任意两点都能互相到达。