問題文

$N$ 頂点 $N - 1$ 辺の無向木が与えられます。 $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を相互に結び、長さは $C_i$ です。

この木のすべての頂点を $1$ 回以上通るパスのうち、最短のものの長さを求めてください。

制約

• $1 \le N \le 10^5$
• $1 \le A_i, B_i \le N$
• $1 \le C_i \le 10^3$
• 入力はすべて整数である

入力

出力

答えを $1$ 行に出力してください。

入出力例

4
1 2 1
2 3 2
2 4 3

7

頂点を $3 \to 2 \to 1 \to 2 \to 4$ の順番で、あるいは、その逆の順番で移動するのが最善です。

出発した頂点に戻る必要はないことに注意してください。

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

15