In Toronto, the TTC operates a commuter train network with $N$ stations connected by $N-1$ bidirectional tracks. The stations are connected such that every pair of stations are connected by travelling along a sequence of tracks. Each track takes $1$ minute to traverse.

Union Station is the center of the network and is labelled node $1$. Given the city's geography, all the tracks radiate outwards from downtown from west to east. The stations are numbered in ascending order based on its distance to Union Station. Stations that are at the same distance are numbered from west to east.

To improve the efficiency of the network, the TTC is considering adding a "crosstown" line, which will consist of a series of tracks that connect adjacent nodes that are the same distance from Union Station. Each track in the line will also take $1$ minute to traverse. To decide on the location of the line, they decide to ask $Q$ queries. In the $i$th query, they want to find the minimum time it takes for a commuter to travel from station $a_i$ to $b_i$ if the line was built at distance $d_i$. Can you write a program to answer them?

Constraints

For all subtasks:

$1\le a_i,b_i,d_i\le N$

$a_i\ne b_i$ for all $1\le i\le N$

Points Awarded	$N$	$Q$
2 points	$3\le N\le 300$	$1\le Q\le 5\times {10}^5$
2 points	$3\le N\le 2\times {10}^3$	$1\le Q\le 2\times {10}^3$
11 points	$3\le N\le 2\times {10}^3$	$1\le Q\le 5\times {10}^5$

Input Specification

The first line of input contains two integers $N$ and $Q$.

The next $N-1$ lines each contain two integers $u$ and $v$, indicating a track connecting stations $u$ and $v$.

The next $Q$ lines each contain three integers $a_i$, $b_i$ and $d_i$.

Output Specification

For each query, output the minimum time in minutes on a separate line.

Sample Input

9 4
1 2
1 3
1 4
2 5
2 6
4 7
7 8
7 9
2 8 2
6 5 2
5 4 2
1 7 4

Sample Output

3
1
3
2

Explanation for Sample Output

Initially, the train network looks like this:

If the line was built at distance $2$ (the added tracks are coloured red), the network would look like this:

For the first query, the passenger can travel from $2⟶6⟶7⟶8$ in $3$ minutes.

For the second query, station $6$ is directly connected to station $5$, thus only taking $1$ minute to travel.

For the third query, the passenger can travel from $5⟶6⟶7⟶4$ in $3$ minutes. Notice that the passenger can also travel from $5⟶2⟶1⟶4$ in the same amount of time.

For the fourth query, the passenger can travel from $1⟶4⟶7$ in $2$ minutes. There are no stations at a distance of $4$ so no new tracks would be added.