货物运输

题目描述

A 国有 座城市，依次以 编号，其中 号城市为⾸都。这 座城市由 条双向道路连接，第 条道路 （ ）连接编号为 的两座城市，道路长度为 。任意两座城市间均可通过双向道路到达。 现在 A 国需要从⾸都向各个城市运送货物。具体来说，满载货物的车队会从⾸都开出，经过⼀座城市时将对应的货 物送出，因此车队需要经过所有城市。A 国希望你设计⼀条路线，在从⾸都出发经过所有城市的前提下，最⼩化经 过的道路长度总和。注意⼀座城市可以经过多次，车队最后可以不返回⾸都。

输入格式

第⼀⾏，⼀个正整数 ，表⽰ A 国的城市数量。 接下来 ⾏，每⾏三个整数 ，表⽰⼀条双向道路连接编号为 的两座城市，道路长度为 。

输出格式

⼀⾏，⼀个整数，表⽰你设计的路线所经过的道路长度总和。

样例输入 #1

4
1 2 6
1 3 1
3 4 5

样例输出 #1

18

样例输入 #2

7
1 2 1
2 3 1
3 4 1
7 6 1
6 5 1
5 1 1

样例输出 #2

9

数据范围

对于 % 的测试点，保证 。 对于另外 % 的测试点，保证仅与⼀条双向道路连接的城市恰有两座。 对于所有测试点，保证 ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。