题目描述

A 国有 $n$ 座城市，编号依次为 $1,2,\dots,n$，其中 $1$ 号城市为首都。这 $n$ 座城市由 $n-1$ 条双向道路连接，第 $i$ 条道路连接编号为 $u_i, v_i$ 的两座城市，道路长度为 $l_i$。任意两座城市间均可通过这些道路互相到达。

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

例如，对于如下所示的树（边上的数字表示长度）：

   1
  / \
 6   1
/     \
2      3
        \
         5
          \
           4

从首都 $1$ 出发，一种最优路线为 $1 \to 3 \to 4 \to 3 \to 1 \to 2$，经过的道路长度依次为 $1,5,5,1,6$，总和为 $1+5+5+1+6=18$。可以证明无法获得更小的总长度。

输入格式

第一行输入一个正整数 $n$，表示城市数量。

接下来 $n-1$ 行，每行输入三个正整数 $u_i, v_i, l_i$，表示一条连接城市 $u_i$ 和 $v_i$ 的双向道路，长度为 $l_i$。

输出格式

输出一行一个整数，表示路线经过的道路长度总和的最小值。

样例

4
1 2 6
1 3 1
3 4 5

18

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

9

数据范围与提示

• 对于 $30\%$ 的测试点：$1 \le n \le 8$。
• 对于另外 $30\%$ 的测试点：仅与一条双向道路连接的城市恰有两座（即树是一条链）。
• 对于所有测试点：$1 \le n \le 10^5$，$1 \le u_i, v_i \le n$，$1 \le l_i \le 10^9$。