旅行
你在一颗树上旅行。
树由N个点，N-1条边组成，每条边的长度是1或2。你想要从点u沿着唯一的简单路径走到点v。但是，你的体力有限，所以一天之内最多只能走p的距离。一天结束时待在树的节点外是很危险的，所以你必须在一天结束前到达某个节点并停下（可以刚好到达），即使你没有走到p的距离。
给定这棵树和Q个询问，每个询问给出u,v,p，请求出至少需要多少天。
Input
第一行两个整数N,Q。
接下来N行每行三个整数x,y,c表示树上有一条x到y的边，长度是c。
接下来Q行每行三个整数u,v,p表示一个询问。
Output
Q行每一行一个整数表示答案。
Examples
| travel.in | travel.out |
|---|---|
| 5 5 | 1 |
| 1 2 1 | 2 |
| 2 3 2 | 1 |
| 1 4 2 | |
| 4 5 1 | |
| 1 5 3 | |
| 1 3 2 | |
| 2 5 4 | |
| 1 2 10 | |
| 4 5 2 |
样例2 travel.in/out 见下发文件。
Notes
对于所有数据，1<=N,Q<=10^5 1<=x,y,u,v<=N c=1或2 2<=p<=2*N
Subtask 1(15pts): c=1
Subtask 2(15pts): 1<=N,Q<=5*10^3
Subtask 3(40pts): 1<=N,Q<=4*10^4
Subtask 4(30pts): 无特殊限制