1433: 邀请卡分发
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：18
题目描述
AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。
但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。
假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。
请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？
但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。
假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。
请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？
输入
输入文件的第一行包含两个整数P和Q （1<=P,Q<=50000）。P为车站总数（包含AMS公司），Q为公共汽车线路数目。接下来有Q行，每行表示一条线路，包含三个数：起点，终点和车费。所有线路上的车费是正整数，且总和不超过1000000000。并假设任何两个车站之间都可到达。
输出
输出文件仅有一行为公司花在分发邀请卡员工交通上的最少费用。
样例输入 复制
2 2
1 2 13
2 1 33
样例输出 复制
46提示
Sample Input2
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
Sample Output2
210