Píngjūn shù wèntí

Task

You are given a tree with $N$ nodes, labeled from $1$ to $N$, where each edge has an integer weight. We define the distance between nodes $a$ and $b$ as the sum of weights on the unique simple path that connects them.

You are also given $Q$ queries of the form $K\ L\ R$, where you have to determine the shortest distance between node $K$ and any node between $L$ and $R$, inclusive.

Input data

The first line of stdin contains two space-separated integers, $N$ and $Q$.

Each of the next $N-1$ lines of stdin contains three space-separated integers, $a$, $b$ and $c$, representing a weighted edge connecting nodes $a$ and $b$ with weight $c$.

Each of the next $Q$ lines of stdin contains three space-separated integers, $K$, $L$ and $R$, representing a query, as described above.

Output data

Each of the next $Q$ lines of stdout will contain an integer $D$, representing the shortest distance to any node between $L$ and $R$, inclusive.

Constraints and clarifications

• $1 \leq N, Q \leq 300 \ 000$;
• $1 \leq a_i, b_i \leq N$;
• $1 \leq c_i \leq 10 \ 000$;

Example 1

stdin

5 3
1 2 10
2 3 10
3 4 10
4 5 10
1 3 5
3 1 2
2 4 5

stdout

20
10
20

Explanation

In the first sample case, the solutions are nodes $3$, $2$ and $4$ for each of the queries.

Example 2

stdin

6 3
1 2 5
1 3 10
1 4 2
1 5 8
1 6 3
2 4 6
4 2 3
3 5 6

stdout

7
7
13

Explanation

In the second sample case, the solutions are nodes $4$, $2$ and $6$ for each of the queries.

Example 3

stdin

3 1
1 2 5
1 3 5
1 2 3

stdout

5

Explanation

In the third sample case, the solution is node $2$.