간선에 양의 가중치가 부여된 N개의 정점으로 구성된 트리가 있다.

M개의 정점 쌍 (u, v)에 대해, 트리 내 두 정점 사이의 유일한 경로 길이(가중치 합)를 각각 출력하라.

입력

첫째 줄에 노드의 개수 \(N\)과 거리를 알고 싶은 노드 쌍의 개수 \(M\)이 입력되고 다음 \(N-1\)개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다.

그 다음 줄에는 거리를 알고 싶은 \(M\)개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

\(M\)개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

제한

- 2≤N≤1,000


- 1≤M≤1,000


- 트리 상에 연결된 두 점과 거리는 10,000이하인 자연수이다.


- 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7