철도

몇 년 전, 바이트랜드(Byteland) 정부는 대중교통을 좀 더 편리하게 만들기 위해 철도망을 건설하기로 했다. 그러나 예산이 넉넉하지 않았기 때문에, 교통부 장관은 철도망을 최대한 단순하게 만들고자 했고 다음 조건을 모두 만족해야 했다.

• 각 열차는 정확히 두 도시를 직접 연결하며, 중간 정차역은 없다.
• 각 열차는 양방향으로 운행하고, 두 방향의 요금은 같다.
• 임의의 도시에서 다른 임의의 도시로 (환승을 포함하여) 이동할 수 있다.
• 열차의 수는 가능한 한 적다.

가장 적은 수의 열차로 모든 도시를 연결하므로, 두 도시 사이의 경로는 항상 유일하다.

이제 철도망이 완성되었다. 남은 골칫거리는 표를 발권하는 일이다. 승객이 A에서 B까지 여러 열차를 갈아타며 이동하면, 직원이 그 열차들의 요금을 일일이 손으로 더해야 하는데 이는 번거롭고 실수하기도 쉽다. 이를 해결하기 위해, 표의 요금을 자동으로 계산하는 프로그램을 작성해야 한다.

프로그램은 먼저 철도망의 구성과 각 열차의 요금을 입력받는다. 그다음 여러 개의 질의에 답해야 한다. 각 질의는 두 도시 $x$와 $y$로 주어지며, 답은 $x$에서 $y$까지 가는 표의 요금, 즉 두 도시를 잇는 경로 위에 있는 열차 요금의 총합이다.

첫째 줄에 두 정수 $N$과 $Q$가 공백 하나로 구분되어 주어진다. $N$은 도시의 수이고 ($1 \le N \le 100\,000$), $Q$는 질의의 수이다 ($1 \le Q \le 2\,000\,000\,000$). 도시는 $1$번부터 $N$번까지 번호가 매겨져 있다.

다음 $N-1$개의 줄에는 각 열차의 정보가 세 정수 $a_i$, $b_i$, $c_i$로 주어지며 공백으로 구분된다 ($1 \le a_i, b_i \le N$, $0 \le c_i \le 2\,000\,000\,000$). 이는 도시 $a_i$와 도시 $b_i$를 잇는 요금 $c_i$의 열차가 있음을 뜻한다. 철도망은 항상 트리를 이룸이 보장된다.

그다음 $Q$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어진다 ($1 \le x_i, y_i \le N$, $x_i \ne y_i$). 요금을 계산해야 하는 두 도시이다.

정확히 $Q$개의 줄을 출력한다. $i$번째 줄에는 정수 하나, 즉 $x_i$에서 $y_i$까지 가는 표의 요금을 출력한다. 모든 요금은 32비트 부호 있는 정수 범위에 들어감이 보장된다.