Taco's Tree Queries

In this problem, you are given an undirected tree with (n) nodes and (n-1) edges. Each edge has a positive weight. For each query, you are required to compute the shortest distance between two given nodes, (a) and (b), along the unique path that connects them. The distance between two nodes is defined as (d(u,v)=\sum_{e \in \text{path}(u,v)} w_e), where (w_e) is the weight of edge (e).

Note that the input is provided via standard input and the output should be written to standard output.

inputFormat

The first line contains two integers (n) (the number of nodes) and (q) (the number of queries).

The next (n-1) lines each contain three integers (u), (v), and (w), representing an undirected edge between nodes (u) and (v) with weight (w).

The following (q) lines each contain two integers (a) and (b), indicating a query to compute the shortest distance between nodes (a) and (b).

outputFormat

For each query, output a single line containing the shortest distance between the two queried nodes.## sample

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

8
9
9