畀你一棵有 $N$ 個頂點嘅樹，頂點依次編號為 $1$ 至 $N$。對 $1\le i\le N-1$，第 $i$ 條邊連接頂點 $A_i$ 同 $B_i$，權重為 $C_i$。

樹上兩個頂點之間嘅傳送距離，係連接佢哋嘅最短路徑上最大嘅邊權重。一個頂點同自己嘅傳送距離定義為 $0$。

住喺樹上嘅人想舉行 $N$ 場會議。第 $i$ 場會議由住喺編號 $1$ 至 $i$ 嘅頂點嘅人參加。今年，由於冠狀病毒傳播，參加者會先到 $X$ 個選定地點，再由嗰啲地點透過互聯網連線。

更正式噉講，對每場會議，我哋會揀 $X$ 個兩兩唔同嘅頂點 $v_1,v_2,\ldots,v_X$。決定頂點之後，每個人會移去 $v_1,\ldots,v_X$ 當中，同佢傳送距離最短嘅一個頂點。對畀定嘅 $X$ 同 $i$，將所有與會者傳送距離嘅最大值定義為會議成本。我哋會選擇頂點 $v_1,\ldots,v_X$，令會議成本盡可能小。

$X$ 嘅值取決於冠狀病毒情況，可能介乎 $1$ 至 $K$。為咗預先準備會議，請寫一個程式，對 $N$ 場會議逐一求出 $X$ 由 $1$ 至 $K$（包括兩端）所有可能值所對應嘅會議成本總和。

輸入

輸入第一行包含兩個整數 $N$ 同 $K$，分別表示頂點數目同 $X$ 嘅上限（$1\le K\le N\le3\cdot10^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