Distance Between Tree Nodes

A weighted tree with N nodes is given. A tree has exactly one path between any two nodes.

For each of M requested pairs of nodes, print the distance between the two nodes. The distance is the sum of edge weights along the unique path connecting them.

The first line contains two integers N and M, where N is the number of nodes and M is the number of node pairs to query.

Each of the next N - 1 lines contains three integers u, v, and d, meaning that nodes u and v are connected by an edge of distance d.

Each of the following M lines contains one pair of nodes whose distance should be printed.

Print M lines. On the i-th line, print the distance between the two nodes in the i-th query.

• 2 <= N <= 1,000
• 1 <= M <= 1,000
• Every edge distance is a natural number not greater than 10,000.
• The tree nodes are numbered with natural numbers from 1 to N, and no two nodes have the same number.