Distance Between Vertices

You are given a weighted tree with N vertices. Then M pairs of vertices are given. For each pair, output the length of the path between the two vertices.

• 2 <= N <= 40,000
• 1 <= M <= 10,000

The first line contains the number of vertices N. Each of the next N - 1 lines contains two vertices connected by an edge and the distance of that edge.

The next line contains the number of queries M. Each of the next M lines contains one pair of vertices whose distance should be found.

Vertices are numbered from 1 to N. Each edge distance is a positive integer no greater than 10,000.

For each of the M queries, output the distance between the given two vertices on its own line, in input order.