题目描述

许多学生被雇来分发请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天，邀请人们参与。 这里的公交系统是非常特殊的：共有 n 个站点和 m 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。 学生每天早上从总部所在的 1 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入格式

输入的第一行是两个整数，代表站点个数 n 和线路条数 m。 第 2 到第 (m+1) 行，每行三个整数 u,v,w，代表存在一条从 u 出发到达 v 的线路，费用为 w。

输出格式

输出一行一个整数，表示最小费用。

样例

输入样例 1

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

输出样例 1

210

输入样例 2

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

输出样例 2

83

输入样例 3

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

输出样例 3

14

提示

数据规模：数据保证：1≤n,m≤10^6。1≤u,v≤n，1≤w≤10^9。从 1 出发可以到达所有的站点。

思路：单源最短路径题。 在建图时同时建正向图1+反向图1，然后各跑一遍 Dijkstra（或其他单源最短路算法），各把 1 到其他点的花费都加起来就好了。 注意：累加的值用 long long。