Problem Description

This problem is a translation from CEOI 2024 Day2 T2「Petrol stations」

The Czech highway network consists of $N$ cities and $N-1$ roads, each with a known length in kilometers. It is known that there is exactly one path between any two cities. Additionally, each city has exactly one petrol station, and no other places have petrol stations.

One day, many people decided to go on a road trip. There are a total of $N^2$ cars on the road. Strangely, for each ordered pair of cities $(a, b)$, exactly one car travels from city $a$ to city $b$ along the unique path between these two cities. Since all Czech people drive Skoda cars, each car has a fuel tank capacity of $K$ liters, and consumes one liter of fuel per kilometer. Before departure, each car's fuel tank is full. Moreover, Czech people are very disciplined. Due to laziness, they only refuel when they do not have enough fuel to reach the next city (they can enter a city with an empty tank). Once they are forced to stop at a petrol station, they always fill their tank to the brim.

The Czech tax authorities want to know how many cars stopped at each petrol station that day. Given this predictable behavior, you should be able to calculate this easily.

Input Format

The first line of input contains two space-separated integers $N$ and $K$, representing the number of cities and the fuel tank capacity of each car, respectively.

The next $N-1$ lines describe the roads. Each line contains three space-separated integers $u_i, v_i, l_i$, where $u_i$ and $v_i$ are the city numbers connected by the $i$-th road, and $l_i$ is the length of this road in kilometers. Cities are numbered from $0$ to $N-1$. It is guaranteed that there is exactly one path between any two cities.

Output Format

Output $N$ lines, representing the number of cars that stopped at the petrol station in each city from city $0$ to city $N-1$.

Sample Input and Output

Sample Input #1

3 1
0 1 1
1 2 1

Sample Output #1

0
2
0

Sample Input #2

6 2
0 1 1
1 2 1
2 3 1
3 4 2
4 5 1

Sample Output #2

0
3
3
12
8
0

Notes/Hints

Sample Explanation 1

There are $3$ cities arranged in a straight line, with the roads connecting them having a length of $1$ kilometer, and the fuel tank capacity is $1$ liter. Only the cars traveling between the outer cities will refuel at the middle city.

Sample Explanation 2

There are $6$ cities arranged in a straight line, with the fuel tank capacity being $2$ liters. Many cars need to refuel at cities $3$ and $4$. This makes sense because the road between cities $3$ and $4$ is $2$ kilometers long.

For all input data, the following conditions are satisfied:
- $2 \leq N \leq 70\,000$
- $1 \leq K \leq 10^9$
- $0 \leq l_i \leq K\ (0 \leq i \leq N-2)$

Let $D$ denote the maximum number of roads connected to a single city. The detailed subtask additional restrictions and scores are as follows:

见题面 Input 部分

见题面 Output 部分