货物运输

题目描述

A 国有 (n) 座城市，依次以 (1, 2, \dots, n) 编号，其中 (1) 号城市为首都。这 (n) 座城市由 (n-1) 条双向道路连接。任意两座城市间均可通过双向道路到达。

满载货物的车队从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。请你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。

输入格式

第一行，一个正整数 (n)，表示 A 国的城市数量。 接下来 (n-1) 行，每行三个整数 (u, v, w)，表示一条双向道路连接编号为 (u) 与 (v) 的两座城市，道路长度为 (w)。

输出格式

一行，一个整数，表示你设计的路线所经过的道路长度总和。

样例

输入样例 1

4
1 2 6
1 3 1
3 4 5

输出样例 1

18

数据范围

对于所有测试点，保证 (1 \le n \le 10^5)，(1 \le w \le 10^4)。

注：原始 PDF 因字体原因丢失了数据范围里的数字，此处重建为 (1 \le n \le 10^5)，(1 \le w \le 10^4)。测试数据使用了较浅深度的树以保证参考程序的递归不超栈。