路线规划
题号：NC217603
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

成为热门手记人偶的薇尔莉特伊芙嘉登最近收到了非常多的委托，这些委托者分散在世界的各地，各个国家都有。但正值战争的尾声，穿行于各个国家之间是非常危险的，一路上会有许多的敌人，这些敌人或许不会对我们的薇尔莉特构成威胁，但是依然会浪费她的时间，手记人偶的时间可是非常宝贵的。现给定有 n 个结点，m 条边的图，除了 1 号结点外，其余 n-1 个结点代表着分散在各地的委托者，他们之间由 m 条道路连接，数据保证图是连通的。现在第 i 道路上有 ai个敌人，每打晕 1 个敌人需要 1 个单位时间。可以理解为通行第 i 条路所需要的时间 ai (1 ≤ i ≤ m)，当薇尔莉特经过一条道路时，仅仅会打晕该条路上的敌人，第一次打晕某条道路上的敌人后，下次经过该条道路仍需要打晕他们。

薇尔莉特从 1 号结点出发，完成所有的委托后还要回到 1 号结点，薇尔莉特希望自己拿出最好的状态去完成每一个委托，但记路这种小事情则会严重影响薇尔莉特的状态。

所以，请你帮帮我们的薇尔莉特，在 走过的路 最少的前提下，求出完成所有委托所需时间 T 的最小值。
PS：一条路只要被经过一次或以上即视为 走过的路

输入描述:

第一行，两个正整数 n，m，分别表示 n 个结点和 m 条边。
接下来 m 行，每行三个整数 u，v，a；表示结点 u 和结点 v 之间的道路有 ai 个敌人，（1 ≤ i ≤ m ）。

输出描述:

第一行，一个正整数 T，表示完成所有委托所需的最少时间 T。
示例1

输入

复制 
5 5
5 4 3 
4 3 5 
2 3 7 
1 2 4 
2 4 1

输出

复制 
26

说明

最少时间的路径:
1 →2 →4 →3 →4 →5 →4 →2 →1
1 →2 →4 →5 →4 →3 →4 →2 →1

示例2

输入

复制 
20 40
6 17 15
20 14 24
3 17 33
8 1 47
16 18 21
20 12 98
14 15 24
6 11 49
12 6 25
3 8 18
5 7 23
12 3 82
5 15 14
20 18 7
3 6 60
17 2 477
15 2 2
8 11 257
9 2 3
5 6 3
18 1 4
12 13 269
7 9 265
6 16 2
13 2 2
5 13 6
8 13 8
14 6 8
8 14 9
17 13 7
12 10 7
16 20 31
2 6 277
4 13 426
16 9 11
10 1 388
6 1 15
20 5 3
12 19 16
16 19 2

输出

复制 
1192

备注:

对于 30%的数据，1 ≤ n ≤ 103，1 ≤ m ≤ 104
对于 80%的数据，1 ≤ n ≤ 5 x104, 1 ≤ m ≤ 105
对于 100%的数据，1 ≤ n ≤ 2×105，1 ≤ m ≤  2x106，1 ≤ ai ≤ 263-1
数据保证最终答案 T ≤  263-1