Description

Given a tree with $n$ nodes, answer multiple queries about the shortest distance between two nodes.

Note: The edges are bidirectional.

Input Format

The first line contains two integers $n$ and $m$. $n$ represents the number of nodes, and $m$ represents the number of queries.

The next $n-1$ lines each contain three integers $x$, $y$, and $k$, indicating that there is an edge between node $x$ and node $y$ with length $k$.

The following $m$ lines each contain two integers $x$ and $y$, representing a query for the shortest distance between node $x$ and node $y$.

Output Format

Output $m$ lines. For each query, output the answer on a separate line.

Sample 1

2 2
1 2 100
1 2
2 1

100
100

Sample 2

3 2
1 2 10
3 1 15
1 2
3 2

10
25

Constraints and Hints

For all data, $2\le n\le 10^4$, $1\le m\le 2\times 10^4$, $0\lt k\le 100$, $1\le x,y\le n$.