給定一棵具有 $N$ 個頂點的樹。頂點編號由 $1$ 至 $N$。第 $i$ 條邊連接頂點 $A_i$ 與 $B_i$，權重為 $C_i$，其中 $1 \le i \le N - 1$。

兩頂點間的「傳送距離」（teleport distance）定義為連接它們的最短路徑上，邊權重的最大值。頂點與自身的傳送距離定義為 $0$。

居住在樹上的居民想要舉辦 $N$ 場會議。第 $i$ 場會議由居住在編號 $1$ 至 $i$ 頂點的居民參加。今年，由於冠狀病毒的傳播，會議參與者將前往 $X$ 個選定的地點，並從這些地點透過網際網路進行連線。

更正式地說，對於每場會議，我們將選擇 $X$ 個兩兩不同的頂點 $v_1, v_2, \dots, v_X$。一旦確定了這些頂點，每個人將移動到與其傳送距離最小的頂點 $v_1, \dots, v_X$ 之一。我們將給定 $X$ 與 $i$ 下的「會議成本」（meeting cost）定義為所有會議參與者傳送距離的最大值。我們將選擇頂點 $v_1, \dots, v_X$ 使得會議成本達到最小。

$X$ 的值取決於冠狀病毒的情況，可能從 $1$ 變動到 $K$。為了提前準備會議，請撰寫一個程式，對於每一場會議（共 $N$ 場），計算所有可能的 $X$ 值（從 $1$ 到 $K$）對應的會議成本總和。

輸入格式

輸入的第一行包含兩個整數 $N$ 與 $K$：分別為頂點數量與 $X$ 的上限 ($1 \le K \le N \le 3 \cdot 10^5$)。

接下來的 $N - 1$ 行描述這棵樹。每一行包含三個整數 $A_i, B_i$ 與 $C_i$，表示頂點 $A_i$ 與 $B_i$ 之間存在一條權重為 $C_i$ 的邊 ($1 \le A_i, B_i, C_i \le N$)。保證給定的圖為一棵樹。

輸出格式

輸出 $N$ 行。在第 $i$ 行，輸出第 $i$ 場會議對於所有 $X$ 從 $1$ 到 $K$ 的會議成本總和。

範例

輸入 1

10 4
5 1 2
1 6 4
6 2 1
2 8 9
8 3 5
3 4 8
4 10 9
10 9 8
9 7 7

輸出 1

0
4
13
21
23
23
30
31
33
34

輸入 2

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

輸出 2

0
8
14
16
16
16
18
18