$N$ 頂点からなる木が与えられる。頂点には $1$ から $N$ までの番号が付けられている。$i$ 番目の辺は頂点 $A_i$ と $B_i$ を結び、重み $C_i$ を持つ ($1 \le i \le N - 1$)。

木上の2頂点間の「テレポート距離」とは、それらを結ぶ最短パス上の辺の重みの最大値である。頂点とそれ自身とのテレポート距離は $0$ と定義される。

木の上に住む人々は $N$ 回の会議を開きたいと考えている。$i$ 番目の会議には、頂点 $1$ から $i$ に住む人々が参加する。今年はコロナウイルスの蔓延により、会議の参加者は $X$ 個の選ばれた場所に集まり、そこからインターネットを通じて接続することになった。

より厳密には、各会議において、$X$ 個の相異なる頂点 $v_1, v_2, \dots, v_X$ を選ぶ。頂点が決定されると、各参加者は自分から最もテレポート距離が近い頂点 $v_1, \dots, v_X$ のいずれかに移動する。与えられた $X$ と $i$ に対する「会議コスト」を、参加者たちのテレポート距離の最大値と定義する。会議コストが最小となるように頂点 $v_1, \dots, v_X$ を選択するものとする。

$X$ の値はコロナウイルスの状況に依存し、$1$ から $K$ まで変化し得る。会議の準備として、各 $i$ 番目の会議について、$X$ が $1$ から $K$ までのすべての値をとるときの会議コストの総和を求めるプログラムを作成せよ。

入力

入力の最初の行には、2つの整数 $N$ と $K$ が含まれる。$N$ は頂点数、$K$ は $X$ の上限である ($1 \le K \le N \le 3 \cdot 10^5$)。

続く $N - 1$ 行は木を記述する。各行には3つの整数 $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