목초지 산책

$N$마리의 소가 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 목초지에서 풀을 뜯고 있습니다 ($2 \le N \le 1{,}000$). 편의상 $i$번 소는 $i$번 목초지에 있습니다.

일부 목초지 쌍은 소들이 지나다닐 수 있는 양방향 산책로로 연결되어 있으며, 산책로는 모두 $N-1$개입니다. $i$번 산책로는 목초지 $A_i$와 $B_i$를 연결하고 ($1 \le A_i \le N$, $1 \le B_i \le N$), 길이는 $L_i$입니다 ($1 \le L_i \le 10{,}000$).

산책로는 서로 다른 임의의 두 목초지 사이에 항상 정확히 하나의 경로가 존재하도록 놓여 있습니다. 즉, 산책로들은 하나의 트리를 이룹니다.

소들은 서로 자주 방문하고 싶어 합니다. 목초지 $Q$쌍 ($1 \le Q \le 1{,}000$)에 대해, 각 질의 $p_1, p_2$ ($1 \le p_1 \le N$, $1 \le p_2 \le N$, $p_1 \ne p_2$)를 잇는 경로의 길이를 구해 주세요.

• 첫째 줄: 두 정수 $N$과 $Q$가 공백으로 구분되어 주어집니다.
• 둘째 줄부터 $N$번째 줄까지: $i+1$번째 줄에는 세 정수 $A_i$, $B_i$, $L_i$가 공백으로 구분되어 주어집니다.
• $N+1$번째 줄부터 $N+Q$번째 줄까지: 각 줄에는 소들이 오가려는 서로 다른 두 목초지 $p_1$과 $p_2$가 공백으로 구분되어 주어집니다.

• $i$번째 줄에 $i$번째 질의에서 주어진 두 목초지 사이 경로의 길이를 출력합니다. (총 $Q$개의 줄)

• 첫 번째 질의: 목초지 $1$과 $2$를 잇는 산책로의 길이는 $2$입니다.
• 두 번째 질의: 목초지 $3$과 $4$를 잇는 산책로, 이어서 $4$와 $1$을 잇는 산책로, 마지막으로 $1$과 $2$를 잇는 산책로를 지나므로 길이는 총 $7$입니다.