Dane jest drzewo o $N$ wierzchołkach. Wierzchołki są ponumerowane kolejno od $1$ do $N$. $i$-ta krawędź łączy wierzchołki $A_i$ oraz $B_i$ i ma wagę $C_i$, dla $1 \le i \le N - 1$.

Odległość teleportacji między dwoma wierzchołkami drzewa to maksymalna waga krawędzi na najkrótszej ścieżce łączącej te wierzchołki. Odległość teleportacji między wierzchołkiem a nim samym wynosi $0$.

Ludzie mieszkający na drzewie chcą zorganizować $N$ spotkań. W $i$-tym spotkaniu biorą udział osoby mieszkające w wierzchołkach o numerach od $1$ do $i$. W tym roku, z powodu rozprzestrzeniania się koronawirusa, uczestnicy spotkania przybędą do $X$ wybranych lokalizacji, a następnie połączą się przez Internet z tych miejsc.

Mówiąc bardziej formalnie, dla każdego spotkania wybierzemy $X$ parami różnych wierzchołków $v_1, v_2, \dots, v_X$. Gdy wierzchołki zostaną wyznaczone, każda osoba uda się do jednego z wierzchołków $v_1, \dots, v_X$, który znajduje się w minimalnej odległości teleportacji od niej. Zdefiniujmy koszt spotkania dla danych $X$ oraz $i$ jako maksimum odległości teleportacji dla uczestników spotkania. Wybierzemy wierzchołki $v_1, \dots, v_X$ w taki sposób, aby koszt spotkania był możliwie najmniejszy.

Wartość $X$ zależy od sytuacji związanej z koronawirusem i może zmieniać się od $1$ do $K$. Aby przygotować się do spotkania z wyprzedzeniem, napisz program, który dla każdego z $N$ spotkań obliczy sumę kosztów spotkań dla wszystkich możliwych wartości $X$ od $1$ do $K$ włącznie.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ oraz $K$: liczbę wierzchołków oraz górny limit dla $X$ ($1 \le K \le N \le 3 \cdot 10^5$).

Kolejne $N - 1$ linii opisuje drzewo. Każda z tych linii zawiera trzy liczby całkowite $A_i$, $B_i$ oraz $C_i$, oznaczające, że istnieje krawędź między wierzchołkami $A_i$ oraz $B_i$ o wadze $C_i$ ($1 \le A_i, B_i, C_i \le N$). Gwarantuje się, że wynikowy graf jest drzewem.

Wyjście

Wypisz $N$ linii. W $i$-tej linii wypisz sumę kosztów spotkań dla $i$-tego spotkania dla wszystkich $X$ od $1$ do $K$ włącznie.

Przykład

Wejście 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

Wyjście 1

0
4
13
21
23
23
30
31
33
34

Wejście 2

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

Wyjście 2

0
8
14
16
16
16
18
18