Weighted Tree Path Sum Query

You are given a tree with N nodes and N-1 edges. Each edge has an associated weight. You will be asked Q queries. In each query, given two nodes u and v, you must find the sum of weights along the unique path connecting u and v in the tree.

For each query, the answer is computed as $$ \text{answer} = \sum_{e \in \text{path}(u,v)} w_e, $$ where \(w_e\) is the weight of edge \(e\). The input guarantees that the given graph forms a tree.

Note: Nodes are numbered from 1 to N, and the tree is rooted at node 1.

inputFormat

The first line contains an integer N denoting the number of nodes in the tree.

The next N-1 lines each contain three space-separated integers u, v, and w, indicating there is an edge between nodes u and v with a weight of w.

The following line contains an integer Q, the number of queries.

Each of the next Q lines contains two integers u and v, representing a query for the sum of weights on the path from node u to node v.

outputFormat

For each query, output a single line containing the sum of weights along the path connecting the two given nodes.

## sample

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

18
15
12

</p>