Data Transfer Time

You are given a network of (n) servers connected by (m) bidirectional links forming a tree. Each link between servers (u) and (v) has an associated transfer time (w). For any two servers (a) and (b), the transfer time is defined as [ T(a,b)=d(a)+d(b)-2,d(\text{LCA}(a,b)) ] where (d(x)) is the cumulative transfer time from the root (server 1) to (x), and (\text{LCA}(a,b)) denotes the lowest common ancestor of (a) and (b) in the tree when rooted at server 1.

Given (q) queries, each asking the transfer time between two servers, compute and output the transfer time for each query.

Note: It is guaranteed that the network forms a tree (i.e. there is exactly one unique path between any two servers).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (n) ( (1 \le n \le 10^5)), the number of servers.
• The second line contains an integer (m) which is equal to (n-1) (since the network forms a tree).
• Each of the next (m) lines contains three integers (u), (v), and (w), representing a bidirectional connection between servers (u) and (v) with a transfer time (w) ((1 \le u,v \le n) and (w \ge 0)).
• The next line contains an integer (q), the number of queries.
• Each of the following (q) lines contains two integers (a) and (b), representing a query asking for the data transfer time between servers (a) and (b).

outputFormat

For each query, output the transfer time on a new line to standard output (stdout).## sample

5
4
1 2 5
1 3 3
2 4 4
2 5 8
3
3 4
4 5
1 5

12
12
13