有 $n$ 座城市,編號由 1 到 $n$。仲有 $n - 1$ 條雙向道路連接呢啲城市,令到對於任意兩座城市 $x$ 同 $y$,都存在一條由 $x$ 去到 $y$ 嘅路徑。第 $i$ 條道路連接城市 $u_i$ 同 $v_i$,費用係 $c_i$。每次你經過第 $i$ 條道路嗰陣,都要花費 $c_i$ 個金幣。
你而家喺城市 1,想去旅行造訪晒所有城市。每一秒,如果你喺城市 $x$,你可以揀一座透過道路同城市 $x$ 直接相連嘅城市 $y$,移動去城市 $y$,並畀相應道路嘅費用。每條道路最多只可以經過兩次。當你造訪晒所有城市並且返到城市 1 嗰陣,就可以結束你嘅旅行。旅行嘅費用係你所做嘅所有移動嘅總費用。
仲有一個整數 $k$。喺旅行期間,你可以使用一次免費優惠券,令你接下來嘅 $k$ 次移動唔使錢。
對於由 0 到 $2n - 2$ 嘅每個 $k$,你應該計算造訪晒所有城市並最優咁使用優惠券嘅旅行最小費用。
輸入格式
第一行包含一個整數 $t$($1 \le t \le 400$),代表測試資料嘅數量。對於每組測試資料:
第一行包含一個整數 $n$($1 \le n \le 2000$),代表城市嘅數量。
跟住落嚟嘅 $n - 1$ 行描述道路。呢啲行入面嘅第 $i$ 行包含三個整數 $u_i$、$v_i$ 同 $c_i$($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$),代表第 $i$ 條道路連接嘅城市同埋嗰條道路嘅費用。
任意兩座城市之間都存在路徑。$n$ 嘅總和唔超過 $2000$。
輸出格式
對於每組測試資料,輸出一行包含 $2n - 1$ 個整數:對於 $k$ 由 0 到 $2n - 2$ 嘅答案。
樣例
輸入
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 |