Migrated from Lutece 735 聚会

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$n$个人打算一起聚会，聚会的地点定在第一个人家里，现在除了第一个人已经在家之外其他人都不在第一个人家里，求$n$个人到第一个人家里的最短路径长度总和。

Input

输入第一行包含两个数$n$, $m$，表示人数和以及连通这个$n$人所在位置的道路数。

接下来的$m$行每行有$3$个数$a_i$, $b_i$, $w_i$，表示第$i$条道路是从第$a_i$个人所在位置指向第$b_i$个人所在位置的单行道(长度为$w_i$)。

其中，$n\le 100000$,$m\le100000$,$w_i\le10000$

Output

输出一个整数，$n$个人的最短路径总长度。

Samples

4 4
2 1 1
3 1 2
4 3 2
3 4 1

7

Resources

2013 UESTC ACM Training for Graph Theory