时间限制：1秒　　内存限制：256M

---

【题目描述】

　　AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。

　　假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？

【输入格式】

　　第一行包含两个整数 \(P\) 和 \(Q\)，\(P\) 为车站总数（包含AMS公司），\(Q\) 为公共汽车线路数目。
　　接下来有 \(Q\) 行，每行表示一条线路，包含三个数：起点，终点和车费。所有线路上的车费是正整数，且总和不超过 \(10^9\)。并假设任何两个车站之间都可到达。

【输出格式】

　　仅有一行为公司花在分发邀请卡员工交通上的最少费用。

【输入输出样例】

　Input

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

　Output

210

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤P≤10000\)，\(1≤Q≤20000\)。

【来源】

　　Mr.he