É dada uma árvore com $N$ vértices. Os vértices estão numerados sequencialmente de $1$ a $N$. A $i$-ésima aresta liga os vértices $A_i$ e $B_i$ e tem peso $C_i$, para $1 \le i \le N - 1$.

A distância de teletransporte entre dois vértices da árvore é o maior peso de uma aresta no caminho mais curto que os liga. A distância de teletransporte entre um vértice e ele próprio é definida como $0$.

Os habitantes da árvore querem realizar $N$ reuniões. Na $i$-ésima reunião participam as pessoas que vivem nos vértices numerados de $1$ a $i$. Este ano, devido à propagação do coronavírus, os participantes irão a $X$ locais selecionados e ligar-se-ão à Internet a partir desses locais.

Mais formalmente, para cada reunião, escolheremos $X$ vértices distintos dois a dois, $v_1, v_2, \ldots, v_X$. Depois de determinar os vértices, cada pessoa deslocar-se-á para um dos vértices $v_1, \ldots, v_X$ cuja distância de teletransporte a ela seja mínima. Definimos o custo da reunião para os valores dados de $X$ e $i$ como a maior distância de teletransporte entre os participantes da reunião. Selecionaremos os vértices $v_1, \ldots, v_X$ de modo que o custo da reunião seja o menor possível.

O valor de $X$ depende da situação do coronavírus e pode variar de $1$ a $K$. Para preparar antecipadamente as reuniões, escreva um programa que, para cada uma das $N$ reuniões, encontre a soma dos custos da reunião para todos os valores possíveis de $X$ de $1$ a $K$, inclusive.

Entrada

A primeira linha da entrada contém dois inteiros $N$ e $K$: o número de vértices e o limite superior de $X$, respetivamente ($1 \le K \le N \le 3 \cdot 10^5$).

As $N - 1$ linhas seguintes descrevem a árvore. Cada uma contém três inteiros $A_i$, $B_i$ e $C_i$, indicando que há uma aresta entre os vértices $A_i$ e $B_i$ com peso $C_i$ ($1 \le A_i, B_i, C_i \le N$). É garantido que o grafo resultante é uma árvore.

Saída

Imprima $N$ linhas. Na linha $i$, imprima a soma dos custos da $i$-ésima reunião para todos os $X$ de $1$ a $K$, inclusive.

Exemplos

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

Saída 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

Saída 2

0
8
14
16
16
16
18
18