트리 거리 쿼리

가중치가 있는 트리가 주어진다. 두 노드 사이의 거리를 묻는 M개의 쿼리에 답하는 프로그램을 작성하시오.

입력

첫째 줄에 노드 수 N과 쿼리 수 M이 공백으로 구분되어 주어진다. (2 ≤ N, M ≤ 1,000) 둘째 줄부터 N-1개의 줄에 간선 정보(a, b, 가중치)가 주어진다. 다음 M개의 줄에 두 노드 번호가 주어진다.

출력

각 쿼리에 대해 두 노드 사이의 거리를 한 줄에 하나씩 출력한다.

입출력 예시

입력 1

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

출력 1

2
7