Gegeben ist ein Baum mit $N$ Knoten. Die Knoten sind fortlaufend von $1$ bis $N$ nummeriert. Für $1\le i\le N-1$ verbindet die $i$-te Kante die Knoten $A_i$ und $B_i$ und hat das Gewicht $C_i$.

Die Teleportdistanz zwischen zwei Knoten des Baums ist das größte Kantengewicht auf dem kürzesten Weg zwischen ihnen. Die Teleportdistanz eines Knotens zu sich selbst ist als $0$ definiert.

Die Bewohner des Baums möchten $N$ Treffen veranstalten. Am $i$-ten Treffen nehmen die Bewohner der Knoten mit den Nummern $1$ bis $i$ teil. Wegen der Ausbreitung des Coronavirus kommen die Teilnehmer dieses Jahr an $X$ ausgewählten Orten zusammen und verbinden sich von dort über das Internet.

Formal wählen wir für jedes Treffen $X$ paarweise verschiedene Knoten $v_1,v_2,\ldots,v_X$. Sobald diese festgelegt sind, begibt sich jede Person zu einem der Knoten $v_1,\ldots,v_X$, zu dem ihre Teleportdistanz minimal ist. Die Kosten des Treffens für gegebene $X$ und $i$ seien das Maximum der Teleportdistanzen aller Teilnehmer. Wir wählen die Knoten $v_1,\ldots,v_X$ so, dass die Kosten des Treffens möglichst klein werden.

Der Wert $X$ hängt von der Coronavirus-Situation ab und kann zwischen $1$ und $K$ liegen. Schreibe zur frühzeitigen Vorbereitung ein Programm, das für jedes der $N$ Treffen die Summe der Kosten für alle möglichen Werte von $X$ von $1$ bis einschließlich $K$ bestimmt.

Eingabe

Die erste Zeile enthält zwei Ganzzahlen $N$ und $K$: die Anzahl der Knoten und die obere Grenze für $X$ ($1\le K\le N\le3\cdot10^5$).

Die folgenden $N-1$ Zeilen beschreiben den Baum. Jede enthält drei Ganzzahlen $A_i,B_i,C_i$ und gibt an, dass zwischen den Knoten $A_i$ und $B_i$ eine Kante mit Gewicht $C_i$ existiert ($1\le A_i,B_i,C_i\le N$). Es ist garantiert, dass der entstehende Graph ein Baum ist.

Ausgabe

Gib $N$ Zeilen aus. Gib in Zeile $i$ die Summe der Kosten des $i$-ten Treffens für alle $X$ von $1$ bis einschließlich $K$ aus.

Beispiele

Eingabe 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

Ausgabe 1

0
4
13
21
23
23
30
31
33
34

Eingabe 2

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

Ausgabe 2

0
8
14
16
16
16
18
18