Un arbre avec $N$ sommets est donné. Les sommets sont numérotés séquentiellement de $1$ à $N$. La $i$-ième arête relie les sommets $A_i$ et $B_i$ et possède un poids $C_i$, pour $1 \le i \le N - 1$.

La distance de téléportation entre deux sommets de l'arbre est le poids maximum d'une arête sur le plus court chemin les reliant. La distance de téléportation entre un sommet et lui-même est définie comme étant $0$.

Les personnes vivant sur l'arbre souhaitent organiser $N$ réunions. La $i$-ième réunion réunit les personnes vivant dans les sommets numérotés de $1$ à $i$. Cette année, en raison de la propagation du coronavirus, les participants à la réunion se rendront à $X$ emplacements sélectionnés, puis se connecteront via Internet depuis ces emplacements.

Plus formellement, pour chaque réunion, nous choisirons $X$ sommets distincts deux à deux $v_1, v_2, \dots, v_X$. Une fois les sommets déterminés, chaque personne se déplacera vers l'un des sommets $v_1, \dots, v_X$ ayant la distance de téléportation minimale vers celui-ci. Définissons le coût de la réunion pour des $X$ et $i$ donnés comme le maximum des distances de téléportation pour les participants à la réunion. Nous choisirons les sommets $v_1, \dots, v_X$ de telle sorte que le coût de la réunion soit le plus petit possible.

La valeur de $X$ dépend de la situation liée au coronavirus et peut varier de $1$ à $K$. Pour préparer la réunion à l'avance, écrivez un programme qui, pour chacune des $N$ réunions, trouve la somme des coûts de réunion pour toutes les valeurs possibles de $X$ de $1$ à $K$, incluses.

Entrée

La première ligne de l'entrée contient deux entiers $N$ et $K$ : le nombre de sommets et la limite supérieure pour $X$, respectivement ($1 \le K \le N \le 3 \cdot 10^5$).

Les $N - 1$ lignes suivantes décrivent l'arbre. Chacune de ces lignes contient trois entiers, $A_i$, $B_i$ et $C_i$, indiquant qu'il existe une arête entre les sommets $A_i$ et $B_i$ avec un poids $C_i$ ($1 \le A_i, B_i, C_i \le N$). Il est garanti que le graphe résultant est un arbre.

Sortie

Imprimez $N$ lignes. Sur la ligne $i$, imprimez la somme des coûts de la $i$-ième réunion pour toutes les valeurs de $X$ de $1$ à $K$, incluses.

Exemples

Entrée 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

Sortie 1

0
4
13
21
23
23
30
31
33
34

Entrée 2

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

Sortie 2

0
8
14
16
16
16
18
18