A - Traveling Salesman on Tree

2 secs 1024 MB
magurofly

問題文


頂点 辺の無向木が与えられます。 番目の辺は頂点 と頂点 を相互に結び、長さは です。

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

制約


  • 入力はすべて整数である

入力


出力


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

入出力例


入力例1
4
1 2 1
2 3 2
2 4 3
出力例1
7

頂点を の順番で、あるいは、その逆の順番で移動するのが最善です。

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

入力例2
6
1 5 1
2 3 3
3 4 1
4 5 5
5 6 4
出力例2
15

提出


Go (1.14)