Problem Description

This problem is translated from CEOI 2024 Day 2 T2「Petrol stations」.

The Czech highway network consists of $N$ cities and $N-1$ roads, and the length (in kilometers) of each road is known. We know that there is exactly one path between any two cities. Also, each city has exactly one petrol station, and there are no petrol stations anywhere else.

One day, many people decide to travel by car. In total, there are $N^2$ cars on the roads. Strangely, for every ordered pair of cities $(a, b)$, there is exactly one car traveling from city $a$ to city $b$, driving along the unique path between these two cities. Since all Czech people drive Škoda cars, every car has a fuel tank capacity of $K$ liters and consumes one liter of fuel per kilometer. Before departure, each car’s tank is full. Also, Czech people are very regular. Due to laziness, they refuel only when they do not have enough fuel to reach the next city (they are allowed to enter a city with an empty tank). Once they are forced to stop at a petrol station, they always fill the tank completely.

The Czech tax authority wants to know how many cars stopped at each petrol station on that day. Given this predictable behavior, you should be able to compute it easily.

Input Format

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

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 indices connected by the $i$-th road, and $l_i$ is the length (in kilometers) of this road. The 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. The $i$-th line should be the number of cars that stopped at the petrol station in city $i$, for cities $0$ to $N-1$.

3 1
0 1 1
1 2 1

0
2
0

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

0
3
3
12
8
0

Hint

Sample Explanation 1.

There are $3$ cities arranged in a straight line. The roads connecting them have length $1$, and the tank capacity is $1$ liter. Only the cars traveling between the two outer cities will refuel in the middle city.

Sample Explanation 2.

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

For all input data, the following constraints hold:

• $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$ be the maximum number of roads connected to a single city. The detailed additional constraints and scores for subtasks are listed in the table below.

Translated by ChatGPT 5