AT_abc361_e [ABC361E] Tree and Hamilton Path 2

[problemUrl]: https://atcoder.jp/contests/abc361/tasks/abc361_e AtCoder国には $ 1 $ から $ N $ の番号がついた $ N $ 個の街と $ 1 $ から $ N-1 $ の番号がついた $ N-1 $ 本の道路があります。 道路 $ i $ は街 $ A_i $ と街 $ B_i $ を双方向に結び、長さは $ C_i $ です。どの街同士も、いくつかの道路を通って互いに行き来することができます。 いずれかの街を出発し、道路による移動で全ての街を $ 1 $ 度以上訪れるための移動距離の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - 入力は全て整数である - どの街同士も、いくつかの道路を通って互いに行き来できる ### Sample Explanation 1 $ 4\ \to\ 1\ \to\ 2\ \to\ 1\ \to\ 3 $ と移動すると移動距離の合計は $ 11 $ となり、これが最小値です。 最初の街に戻ってくる必要はないことに注意してください。 ### Sample Explanation 2 オーバーフローに注意してください。