18584번 - Deliveries 다국어

Sam is working as a truck driver and is frequently delivering goods between various warehouses. There are N warehouses in total. Some warehouses are connected, and there is exactly one way to get from each warehouse to each other warehouse, possibly passing several other warehouses along the way.

To make his trips, Sam will be using various battery-powered trucks. Each truck has a folding solar panel that can be used to charge the battery, but only when the truck is stopped. While traveling from one warehouse to another, Sam can stop at any point and wait a bit to recharge the battery. When the battery is out of charge, he can’t move. Sam must also stop at every warehouse he passes through for security reasons. When he stops at a warehouse, he can also recharge the battery.

Sam doesn’t like to stop too much, so he asked you to find the smallest number of stops for each route he takes. This includes both stops made for recharging and stops at warehouses, including the starting and final warehouses (for loading and unloading).

The first line contains two numbers N and Q, the number of warehouses and the number of routes Sam takes, with 1 ≤ N, Q ≤ 100, 000. The next N − 1 lines describe roads between warehouses. Each line contains 3 numbers: U, V, D. U and V are indices of warehouses, with 1 ≤ U, V ≤ N. D is the length of the road between warehouses U and V in kilometres, with 1 ≤ D ≤ 20, 000. The next Q lines describe the routes Sam takes. Each line contains 3 numbers: S, F, T. S and F are indices of the starting and final warehouses on the route, with 1 ≤ S, F ≤ N and S 6= F. T is the capacity of the battery of the truck used for this route, expressed as the distance that the truck can travel on a full charge (in kilometres). T satisfies 1 ≤ T ≤ 20, 000.

For each of the Q routes, output one line containing the smallest number of stops that need to be made along the route.