정점 사이의 거리

N개의 정점으로 이루어진 가중치가 있는 트리가 주어진다. 이어서 M개의 정점 쌍이 주어질 때, 각 쌍에 대해 두 정점 사이의 경로 길이를 출력하라.

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

첫째 줄에 정점의 개수 N이 주어진다. 다음 N - 1개의 줄에는 트리에서 연결된 두 정점과 그 간선의 거리가 주어진다.

그다음 줄에 질의의 개수 M이 주어진다. 다음 M개의 줄에는 거리를 알고 싶은 두 정점이 한 줄에 하나의 쌍씩 주어진다.

정점 번호는 1번부터 N번까지이다. 각 간선의 거리는 10,000 이하의 자연수이다.

입력된 M개의 질의 순서대로, 각 줄에 해당 두 정점 사이의 거리를 출력한다.