A weighted tree is given. Find the distance between two specified vertices.
The first line contains the number of nodes n (1≤n≤150000) in the tree. Nodes are numbered from 0 to n−1. Each of the following n−1 lines consists of three integers u,v,w representing an edge with weight w (0≤w≤1000), connecting nodes u and v. The next line contains the number of queries m (1≤m≤75000). Each of the next m lines contains two integers — the numbers of vertices between which the distance needs to be computed.
For each query print the distance between the nodes with the given numbers.