In the Stubaj Forest, ants have built $n$ anthills, numbered from 1 to $n$. The anthills are connected by bidirectional underground paths such that there is exactly one way to travel between any two of them (without turning back).

The queen of the Stubaj Forest ants has ordered an annual rotation of the anthill staff. The rotation involves $m$ workers: the $i$-th worker must leave their current anthill $a_i$ at time $t_i$ and head to anthill $b_i$.

All ants travel their path at the same speed, without stopping.

There is a suspicion that if too many marching ants meet at one point on the route, they might secede. Before the workers set off, the queen would like to know for each of them the size of the largest set of other traveling ants that this worker will meet simultaneously (i.e., will be at the same point on a path or within one of the anthills at the same time). We only consider meetings during the journey: more precisely, if the $i$-th ant reaches its destination anthill at time $t'_i$, we only count meetings between ants $i$ and $j$ at times in the interval $[t_i, t'_i] \cap [t_j, t'_j]$.

Input

The first line of input contains two integers $n, m$ ($1 \le n, m \le 100\,000$), representing the number of anthills and the number of ants participating in the rotation, respectively. The next $n-1$ lines describe the network of paths between the anthills. Each of these lines contains three integers $u_i, v_i, d_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le d_i \le 10^9$), indicating that anthills $u_i$ and $v_i$ are connected by a path that takes $d_i$ units of time for a worker to traverse. This is followed by $m$ lines describing the subsequent ants participating in the rotation. The $i$-th line contains three integers $a_i, b_i, t_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le t_i \le 10^9$).

Output

Output $m$ lines. The $i$-th line should contain the size of the largest set of traveling ants (other than $i$) that ant $i$ will meet simultaneously during its journey.

Examples

Input 1

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

Output 1

2
2
2
1
0