有 $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 |