노드 사이의 거리

가중치가 있는 N개의 노드로 이루어진 트리가 주어진다. 트리에서는 임의의 두 노드 사이에 경로가 정확히 하나만 존재한다.

거리를 알고 싶은 노드 쌍이 M개 주어진다. 각 쌍에 대해 두 노드를 잇는 유일한 경로에 포함된 간선 가중치의 합을 출력하라.

첫째 줄에 노드의 개수 N과 거리를 구할 노드 쌍의 개수 M이 주어진다.

다음 N - 1개의 줄에는 정수 u, v, d가 주어진다. 이는 노드 u와 노드 v가 거리 d인 간선으로 연결되어 있음을 뜻한다.

그다음 M개의 줄에는 거리를 구하고 싶은 노드 쌍이 한 줄에 한 쌍씩 주어진다.

M개의 줄을 출력한다. i번째 줄에는 i번째 질의로 주어진 두 노드 사이의 거리를 출력한다.

• 2 <= N <= 1,000
• 1 <= M <= 1,000
• 각 간선의 거리는 10,000 이하인 자연수이다.
• 트리 노드의 번호는 1부터 N까지의 자연수이며, 같은 번호를 가진 노드는 없다.