AT_abc369_g [ABC369G] As far as possible

[problemUrl]: https://atcoder.jp/contests/abc369/tasks/abc369_g $ N $ 頂点からなる木が与えられます。 頂点は頂点 $ 1 $, 頂点 $ 2 $, $ \ldots $, 頂点 $ N $ と番号づけられています。 また、$ i $ 番目（ $ 1\leq\ i\leq\ N-1 $ ）の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでおり、長さは $ L_i $ です。 $ K=1,2,\ldots,\ N $ について次の問題を解いてください。 > 高橋君と青木君がゲームをします。ゲームは次のように行われます。 > > - まず、青木君が木上の相異なる $ K $ 個の頂点を指定します。 > - 次に、高橋君は始点と終点がともに頂点 $ 1 $ であるような歩道であって、青木君が指定した頂点をすべて通るようなものを構成します。 > > 高橋君が構成した歩道の長さをスコアと定義します。高橋君はスコアをなるべく小さく、青木君はスコアをなるべく大きくしたいです。 $ 2 $ 人が最善に行動したときのスコアを求めてください。 歩道とは 無向グラフ（木を含む）上の歩道とは、$ k $ 個 ($ k $ は正整数) の頂点と $ k-1 $ 個の辺を交互に並べた列 $ v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k $ であって、 辺 $ e_i $ が頂点 $ v_i $ と頂点 $ v_{i+1} $ を結んでいるようなものを指す。列の中に同じ頂点や同じ辺が何回登場しても良い。 歩道が頂点 $ x $ を通るとは、$ v_i=x $ となるような $ 1\leq\ i\leq\ k $ が $ 1 $ つ以上存在することをいう。（複数個存在しても良い。） また、歩道の始点、終点はそれぞれ $ v_1 $, $ v_k $ のことをさし、歩道の長さとは $ e_1 $, $ e_2 $, $ \ldots $, $ e_{k-1} $ の長さの総和を表す。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ U_1 $ $ V_1 $ $ L_1 $ $ U_2 $ $ V_2 $ $ L_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ $ L_{N-1} $

$ N $ 行出力せよ。 $ i $ 行目 $ (1\leq\ i\leq\ N) $ には $ K=i $ のときの問題の答えを出力せよ。

### 制約 - $ 2\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ U_i\