Petrol stations

The Czech highway network consists of $N$ cities and $N-1$ roads with known lengths in kilometers. There is exactly one path between each pair of cities. Each city has one petrol station, and there are no other petrol stations.

One day, several people went on a car trip. A total of $N^2$ cars traveled. For each ordered pair of cities $(a,b)$, exactly one car drove from city $a$ to city $b$ along the only path between them. Every car has the same fuel tank capacity of $K$ liters. A car consumes one liter of petrol per kilometer traveled. Before departure, each tank is full.

The Czechs are predictable and lazy. A car refuels only when it does not have enough petrol to reach the next city. It can still enter a city with an empty tank. When a car is forced to stop at a petrol station, it fills the tank completely.

The Czech tax authority wants to know how many cars stopped at each petrol station during the day. Using this predictable behavior, the count can be computed easily.

The first line contains two space-separated integers $N$ and $K$, 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$, and $l_i$, where $u_i$ and $v_i$ are the cities connected by the $i$-th road and $l_i$ is its length in kilometers. Cities are numbered from $0$ to $N-1$. It is guaranteed that there is exactly one path between every pair of cities.

Output $N$ lines. The $i$-th line (starting from city $0$) contains the number of cars that stopped at the petrol station in city $i$.

• $2 \leq N \leq 70000$
• $1 \leq K \leq 10^9$
• $0 \leq l_i \leq K$ (for each $i$ such that $0 \leq i \leq N-2$)