$N$ 個の頂点からなる木 $T$ が与えられる。各辺には正の整数重みがついている。 与えられた木に対して、以下の操作を行うことができる。

• グラフから辺を 1 本削除し、その後、任意の異なる 2 頂点間に新しい辺を追加する。新しい辺の重みは、削除した辺の重みと同じでなければならない。結果として得られるグラフは木である必要はない。

パスの重みを、そのパス上の辺の重みの総和と定義する。2 頂点 $u$ と $v$ の間の距離を、$u$ から $v$ への最短パス（最小重みのパス）の重みと定義する。そのようなパスが存在しない場合、距離は 0 と定義する。 グラフの重みを、任意の 2 頂点間の距離の最大値と定義する。

あなたのタスクは、操作をちょうど $i$ 回行ったときに得られるグラフの最大の重みを、$i = 0, 1, \dots, K$ のそれぞれについて求めることである。

入力

1 行目には、2 つの空白区切りの整数 $N$ と $K$ が与えられる。 続く $N - 1$ 行の $i$ 行目には、3 つの空白区切りの整数 $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

出力 1

14 16

入力 2

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

出力 2

13 20 21