Tree Distance Queries

You are given a tree with n nodes numbered from 1 to n and n-1 edges. Each edge has an associated positive weight. After building the tree, you are to answer q queries. Each query asks for the distance between two given nodes. The distance is defined as the sum of weights along the unique simple path between the two nodes.

This problem requires you to efficiently compute the distance between any two nodes. A common technique to solve this is to perform a Depth First Search (DFS) starting from node 1 to compute the depth, parent, and cumulative distance for each node. Then, for each query, you can compute the Lowest Common Ancestor (LCA) of the two queried nodes and use it to calculate the answer using the formula:

[ \text{distance}(u,v)=\text{dist}[u]+\text{dist}[v]-2\times\text{dist}[\text{LCA}(u,v)] ]

Implement the solution following the guidelines. Your program should read the input from standard input and output the answers on standard output.

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains two integers n and q, where n is the number of nodes and q is the number of queries.
• The next n-1 lines each contain three integers u, v, and w which denote an edge between nodes u and v with weight w.
• The following q lines each contain two integers u and v representing a query to compute the distance between node u and node v.

Input is given via stdin.

outputFormat

For each query in each test case, print a single line containing the distance between the two nodes. The output for each test case's queries should be in the same order as the input queries, and the overall output is written to stdout.

## sample

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

5
10
9

</p>