[ABC361] E - Tree and Hamilton Path 2

E - Tree and Hamilton Path 2

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 500 分

题面

在 AtCoder 国家里，有 个城市，编号从 到 ，有
条道路，编号从 到 。

第 条道路双向连接城市 和 ，长度为 。通过道路，任意两座城市之间都可以互相到达。

找出从某个城市出发，访问所有城市至少一次所需的最短旅行距离。

限制条件

• 所有输入值均为整数。
• 通过道路，任意两座城市之间都可以互相到达。

---

输入

从标准输入中以以下格式给出：

输出

输出答案。

---

输入样例 1

4
1 2 2
1 3 3
1 4 4

输出样例 1

11

若按顺序 行驶，总旅行距离为 ，为最小值。

注意无需返回起始城市。

---

输入样例 2

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

输出样例 2

9000000000

注意溢出问题。