Дано дерево с $N$ вершинами. Вершины пронумерованы последовательно от $1$ до $N$. $i$-е ребро соединяет вершины $A_i$ и $B_i$ и имеет вес $C_i$ для $1 \le i \le N - 1$.

Телепортационным расстоянием между двумя вершинами дерева называется максимальный вес ребра на кратчайшем пути, соединяющем их. Телепортационное расстояние между вершиной и самой собой равно $0$.

Люди, живущие в вершинах дерева, хотят провести $N$ встреч. В $i$-й встрече участвуют люди, живущие в вершинах с номерами от $1$ до $i$. В этом году из-за распространения коронавируса участники встречи прибудут в $X$ выбранных мест, а затем будут общаться через Интернет из этих точек.

Более формально, для каждой встречи мы выберем $X$ попарно различных вершин $v_1, v_2, \dots, v_X$. После того как вершины выбраны, каждый человек переместится в одну из вершин $v_1, \dots, v_X$ с минимальным телепортационным расстоянием до неё. Определим стоимость встречи для заданных $X$ и $i$ как максимум телепортационных расстояний для всех участников встречи. Мы выберем вершины $v_1, \dots, v_X$ таким образом, чтобы стоимость встречи была минимально возможной.

Значение $X$ зависит от ситуации с коронавирусом и может варьироваться от $1$ до $K$. Чтобы подготовиться к встрече заранее, напишите программу, которая для каждой из $N$ встреч находит сумму стоимостей встреч для всех возможных значений $X$ от $1$ до $K$ включительно.

Входные данные

Первая строка входных данных содержит два целых числа $N$ и $K$: количество вершин и верхний предел для $X$ соответственно ($1 \le K \le N \le 3 \cdot 10^5$).

Следующие $N - 1$ строк описывают дерево. Каждая из этих строк содержит три целых числа $A_i$, $B_i$ и $C_i$, означающих, что существует ребро между вершинами $A_i$ и $B_i$ с весом $C_i$ ($1 \le A_i, B_i, C_i \le N$). Гарантируется, что полученный граф является деревом.

Выходные данные

Выведите $N$ строк. В $i$-й строке выведите сумму стоимостей $i$-й встречи для всех $X$ от $1$ до $K$ включительно.

Примеры

Примеры 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

0
4
13
21
23
23
30
31
33
34

Примеры 2

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

0
8
14
16
16
16
18
18