001 - 平成の終焉を告げる

時間制限 1 秒 / メモリ制限 64 MB / 得点 247 / x 0 /


TLE
1sec
MLE
64MB
得点
247

問題

今日をもち、天皇としての務めを終えることになりました。
ただ今、国民を代表して、安倍内閣総理大臣の述べられた言葉に、深く謝意を表します。
即位から30年、これまでの天皇としての務めを、国民への深い信頼と敬愛をもって行い得たことは、幸せなことでした。
象徴としての私を受け入れ、支えてくれた国民に、心から感謝します。
明日から始まる新しい令和の時代が、平和で実り多くあることを、皇后と共に心から願い、ここに我が国と世界の人々の安寧と幸せを祈ります。
── 今上天皇

木が与えられます。
頂点Sからスタートしてすべての辺を訪れ、頂点Sに戻ってきます。
頂点Sを最適に選び、かつ順路を最適に選んだときの最小コストを求めてください。
ただしそのような道がないときはContradictionと出力せよ。

入力

N
a1 b1 c1
......
aN-1 bN-1 cN-1

頂点の数が与えられます。
その後N-1行に渡って辺の情報が与えられます。
これは頂点aから頂点b、頂点bから頂点aまで移動するのにコストcがかかることを示します。

出力

minCost

制約

$2$ ≤ $N$ ≤ $5$ $*$ $10$5
$1$ ≤ $a$, $b$ ≤ $N$
$0$ ≤ $c$ ≤ $1e9$

テストケース

例1

入力

2
1 2 1

出力

2

自明

例2

入力

2
2 1 1

出力

2

自明