Se da un árbol con $N$ vértices. Los vértices están numerados secuencialmente del 1 al $N$. La arista $i$-ésima conecta los vértices $A_i$ y $B_i$, y tiene un peso $C_i$, para $1 \le i \le N - 1$.

La distancia de teletransporte entre dos vértices del árbol es el peso máximo de la arista en el camino más corto que los conecta. La distancia de teletransporte entre un vértice y sí mismo se define como 0.

Las personas que viven en el árbol quieren realizar $N$ reuniones. A la reunión $i$-ésima asisten personas que viven en los vértices numerados del 1 al $i$. Este año, debido a la propagación del coronavirus, los participantes de la reunión llegarán a $X$ ubicaciones seleccionadas y luego se conectarán a través de Internet desde estas ubicaciones.

Más formalmente, para cada reunión, elegiremos $X$ vértices distintos por pares $v_1, v_2, \dots, v_X$. Una vez determinados los vértices, cada persona se moverá a uno de los vértices $v_1, \dots, v_X$ con la distancia de teletransporte mínima hacia él. Definamos el costo de reunión para los $X$ e $i$ dados como el máximo de las distancias de teletransporte para los participantes de la reunión. Seleccionaremos los vértices $v_1, \dots, v_X$ de tal manera que el costo de la reunión sea el mínimo posible.

El valor de $X$ depende de la situación del coronavirus y puede variar de 1 a $K$. Para preparar la reunión con antelación, escriba un programa que, para cada una de las $N$ reuniones, encuentre la suma de los costos de reunión para todos los valores posibles de $X$ desde 1 hasta $K$, inclusive.

Entrada

La primera línea de la entrada contiene dos enteros $N$ y $K$: el número de vértices y el límite superior para $X$, respectivamente ($1 \le K \le N \le 3 \cdot 10^5$).

Las siguientes $N - 1$ líneas describen el árbol. Cada una de estas líneas contiene tres enteros, $A_i$, $B_i$ y $C_i$, indicando que hay una arista entre los vértices $A_i$ y $B_i$ con peso $C_i$ ($1 \le A_i, B_i, C_i \le N$). Se garantiza que el grafo resultante es un árbol.

Salida

Imprima $N$ líneas. En la línea $i$, imprima la suma de los costos de reunión de la $i$-ésima reunión para todos los $X$ desde 1 hasta $K$, inclusive.

Ejemplos

Entrada 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

Salida 1

0
4
13
21
23
23
30
31
33
34

Entrada 2

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

Salida 2

0
8
14
16
16
16
18
18