1 から $n$ までの番号がついた $n$ 個の都市があります。また、これらの都市を結ぶ $n - 1$ 本の双方向道路があり、任意の 2 つの都市 $x$ と $y$ について $x$ から $y$ への単純道が存在します。$i$ 番目の道路は都市 $u_i$ と $v_i$ を結び、コスト $c_i$ を持ちます。道路 $i$ を通るたびに $c_i$ 枚のコインを消費します。
あなたは現在都市 1 にいて、すべての都市を訪れる旅行をしたいと考えています。毎秒、都市 $x$ にいるとき、道路で都市 $x$ と直接結ばれている都市 $y$ を 1 つ選び、都市 $y$ に移動して対応する道路のコストを支払うことができます。各道路は高々 2 回しか通ることができません。すべての都市を訪れ、かつ都市 1 に戻ってきたとき、旅行を終えることができます。旅行のコストは行ったすべての移動のコストの合計です。
また、整数 $k$ があります。旅行中に 1 回だけ無料クーポンを使うことができ、その後の $k$ 回の移動のコストを 0 にすることができます。
0 から $2n - 2$ までのすべての $k$ について、すべての都市を訪れ、クーポンを最適に使ったときの旅行の最小コストを求めてください。
入力
1 行目には、テストケースの個数を表す 1 つの整数 $t$ ($1 \le t \le 400$) が与えられます。各テストケースについて:
1 行目には、都市の個数を表す整数 $n$ ($1 \le n \le 2000$) が与えられます。
続く $n - 1$ 行は道路を記述します。これらのうち $i$ 行目には、$i$ 番目の道路が結ぶ都市とその道路のコストを表す 3 つの整数 $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$) が与えられます。
任意の 2 都市間には経路が存在します。$n$ の総和は $2000$ を超えません。
出力
各テストケースについて、0 から $2n - 2$ までの $k$ に対する答えである $2n - 1$ 個の整数を 1 行に出力してください。
入出力例
入力
2 5 1 2 2 2 3 3 2 4 1 4 5 3 7 1 2 1 1 3 1 1 4 4 3 5 5 3 6 1 6 7 4
出力
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
注記
最初のテストケースでは、常に経路 $1, 2, 3, 2, 4, 5, 4, 2, 1$ に沿って旅行することができ、そのコスト列は $2, 3, 3, 1, 3, 3, 1, 2$ です。各 $k$ に対する無料区間は以下の通りです。
| $k$ | 無料区間 | 答え |
|---|---|---|
| 0 | $[]$ | 18 |
| 1 | $[3]$ | 15 |
| 2 | $[3, 3]$ | 12 |
| 3 | $[2, 3, 3]$ | 10 |
| 4 | $[3, 3, 1, 3]$ | 8 |
| 5 | $[3, 3, 1, 3, 3]$ | 5 |
| 6 | $[2, 3, 3, 1, 3, 3]$ | 3 |
| 7 | $[2, 3, 3, 1, 3, 3, 1]$ | 2 |
| 8 | $[2, 3, 3, 1, 3, 3, 1, 2]$ | 0 |