Petrol Stations

This problem is adapted from CEOI 2024 Day2 T2 "Petrol Stations".

The Czech highway network forms a tree consisting of \(N\) cities and \(N-1\) roads. Each road has a given length in kilometers. It is known that between any two cities there exists exactly one path. Moreover, each city has exactly one petrol station and there are no other stations.

On a certain day, \(N^2\) cars take to the road. Interestingly, for every ordered pair of cities \((a,b)\) there is exactly one car that drives from city \(a\) to city \(b\) along the unique path between them. Since all cars are from the same manufacturer, each has a fuel tank capacity of \(K\) liters and consumes exactly 1 liter per kilometer. Before the journey, every car starts with a full tank.

The Czech drivers are extremely disciplined. They refuel only when they do not have enough fuel to reach the next city. (Note that arriving at a city with an empty tank is allowed.) When forced to stop, the driver always refuels to a full tank.

Your task is to determine the total number of cars that stop to refuel at each petrol station during that day.

Fueling rule: When a car is at a city with current fuel \(f\) and the edge to the next city requires a fuel amount \(d\): if \(f < d\) then the car stops at the current city, refuels (i.e. resets fuel to \(K\)), and then proceeds (consuming \(d\) liters for that road). Otherwise, it proceeds without refueling (and the fuel decreases by \(d\)).

Note that for the trivial journey when \(a = b\) (i.e. no travel) no fuel stop occurs.

inputFormat

The first line contains two integers \(N\) and \(K\) \((2 \leq N,\ K \leq \text{small enough})\) — the number of cities and the fuel tank capacity of each car respectively.

Each of the following \(N-1\) lines contains three integers \(u\), \(v\) and \(d\) indicating that there is a bidirectional road between cities \(u\) and \(v\) with length \(d\) kilometers.

The cities are numbered from 1 to \(N\). It is guaranteed that the given roads form a tree.

outputFormat

Output a single line containing \(N\) integers. The \(i\)th integer should be the total number of cars that refueled at the petrol station located in city \(i\) during the day.

sample

3 10
1 2 5
2 3 6

0 2 0