题目描述

《数据规模》

【Tree and Hamilton Path 2】 在 AtCoder 国有 1 到 N 编号的 N 个城市，以及 1 到 N-1 编号的 N-1 条道路。 第 i 条道路连接城市 Ai 和城市 Bi，是双向的，长度为 Ci。任意两个城市之间都可以通过若干条道路互相到达。 请你求出，从任意一个城市出发，通过道路移动，访问所有城市至少一次所需的最小移动距离。

输入格式

输入通过标准输入按以下格式给出。 N A1 B1 C1 ... A(N-1) B(N-1) C(N-1)

输出格式

输出最小移动距离。

样例

输入样例 1

4
1 2 2
1 3 3
1 4 4

输出样例 1

11

输入样例 2

5
1 2 1
1 3 2
1 4 3
1 5 4

输出样例 2

13

输入样例 3

4
1 2 1
2 3 10
3 4 100

输出样例 3

111

输入样例 4

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

输出样例 4

49