408074: GYM102979 B Best Meeting Places

A tree with $$$N$$$ vertices is given. Vertices are numbered sequentially from $$$1$$$ to $$$N$$$. The $$$i$$$-th edge connects vertices $$$A_i$$$ and $$$B_i$$$, and has weight $$$C_i$$$, for $$$1 \leq i \leq N - 1$$$.

The teleport distance between two vertices of the tree is the maximum weight of the edge on the shortest path connecting them. The teleport distance between a vertex and itself is defined as $$$0$$$.

People living on the tree want to hold $$$N$$$ meetings. The $$$i$$$-th meeting is attended by people living in the vertices numbered from $$$1$$$ to $$$i$$$. This year, because of the spread of coronavirus, the meeting participants will arrive at $$$X$$$ selected locations, and then connect via Internet from these locations.

More formally, for each meeting, we will choose $$$X$$$ pairwise distinct vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_X$$$. Once the vertices are determined, each person will move to one of the vertices $$$v_1$$$, $$$\ldots$$$, $$$v_X$$$ with the minimum teleport distance to it. Let us define the meeting cost for the given $$$X$$$ and $$$i$$$ as the maximum of teleport distances for meeting participants. We will select the vertices $$$v_1$$$, $$$\ldots$$$, $$$v_X$$$ in such a way that the meeting cost is minimal possible.

The value of $$$X$$$ depends on the coronavirus situation, and may vary from $$$1$$$ to $$$K$$$. To prepare for the meeting in advance, write a program that, for each of the $$$N$$$ meetings, finds the sum of the meeting costs for all possible values of $$$X$$$ from $$$1$$$ to $$$K$$$, inclusive.

The first line of input contains two integers $$$N$$$ and $$$K$$$: the number of vertices and the upper limit for $$$X$$$, respectively ($$$1 \leq K \leq N \leq 3 \cdot 10^5$$$).

The following $$$N - 1$$$ lines describe the tree. Each of these lines contains three integers, $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$, telling that there is an edge between vertices $$$A_i$$$ and $$$B_i$$$ with weight $$$C_i$$$ ($$$1 \leq A_i, B_i, C_i \leq N$$$). It is guaranteed that the resulting graph is a tree.

Print $$$N$$$ lines. On line $$$i$$$, print the sum of meeting costs of $$$i$$$-th meeting for all $$$X$$$ from $$$1$$$ to $$$K$$$, inclusive.

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

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