Ants

In the Hundred Byte Wood, the ants have built $n$ anthills numbered $1$ through $n$. The anthills are connected by two-way tunnels so that there is exactly one simple path between each pair of anthills.

Spring has come, and the queen ant announced an annual rotation of the anthill structure. The rotation involves $m$ worker ants. The $i$-th ant must leave its anthill $a_i$ at time $t_i$ and travel to anthill $b_i$ along the shortest path. All ants move at the same speed, and none of them stops before reaching its destination.

The queen suspects that too many ants meeting at one point could start a secession. For each worker ant, find the largest number of other travelling ants that this worker meets at a single point, either inside a tunnel or at an anthill. Meetings happen only during travel. If the $i$-th ant arrives at its destination at time $t_i'$, then ants $i$ and $j$ can meet only at a time $t$ in $[t_i, t_i'] \cap [t_j, t_j']$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 100\,000$), the number of anthills and the number of worker ants.

Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$, $d_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le d_i \le 10^9$). This means anthills $u_i$ and $v_i$ are connected by a two-way tunnel, and a worker needs $d_i$ time units to pass through it.

Each of the last $m$ lines contains three integers $a_i$, $b_i$, $t_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le t_i \le 10^9$) describing a worker ant.

Print $m$ lines. The $k$-th line contains the largest number of travelling ants (other than ant $k$) that ant $k$ meets at the same time.