給定一棵包含 $N$ 個頂點的樹 $T$，每條邊都有一個正整數權重。

你可以對給定的樹執行以下操作：

• 從圖中刪除一條邊，然後在任意兩個不同的頂點之間添加一條新邊。新邊的權重必須與被刪除邊的權重相同。結果圖不一定需要是一棵樹。

我們將路徑的權重定義為該路徑上所有邊的權重總和。兩個頂點 $u$ 和 $v$ 之間的距離定義為從 $u$ 到 $v$ 的最短路徑（即權重最小的路徑）的權重。如果不存在這樣的路徑，我們將距離定義為 $0$。

圖的權重定義為任意兩個頂點之間距離的最大值。

你的任務是找出在執行操作恰好 $i$ 次後，圖所能獲得的最大權重，其中 $i = 0, 1, \dots, K$。

輸入格式

第一行包含兩個以空格分隔的整數 $N$ 和 $K$。

接下來的 $N - 1$ 行中，第 $i$ 行包含三個以空格分隔的整數 $u_i$、$v_i$ 和 $w_i$，表示一條連接兩個不同頂點 $u_i$ 和 $v_i$ 的無向邊，其權重為 $w_i$。

保證這些邊構成一棵樹。

• $2 \le N \le 2000$
• $0 \le K \le 2000$
• $1 \le u_i < v_i \le N$ ($1 \le i \le N - 1$)
• $1 \le w_i \le 10^9$ ($1 \le i \le N - 1$)

輸出格式

輸出 $K + 1$ 個以空格分隔的整數。第 $i$ 個整數應等於執行操作恰好 $i - 1$ 次後，圖所能獲得的最大權重。

範例

範例 1

輸入

5 1
1 3 2
4 5 4
3 4 3
2 3 7

輸出

14 16

範例 2

輸入

7 2
1 2 4
2 3 6
2 4 2
4 5 5
2 6 1
4 7 3

輸出

13 20 21