도시 운전

최근 여가 시간에 샌프란시스코를 자주 다니기 시작했는데, 도심에서 운전하는 일이 여간 번거로운 게 아니라는 것을 깨달았습니다. 하지만 관심 있는 장소는 $N$개뿐이므로, 운전을 좀 더 편하게 만들어 보기로 했습니다. GPS가 없고 여러 경로를 외우기도 어렵기 때문에, $N$쌍의 장소 사이를 오가는 길과 걸리는 시간을 적어 두었습니다. 각 경로는 양방향이며(어느 방향으로 가든 걸리는 시간이 같습니다), 이 경로들만 이용해도 임의의 장소에서 다른 임의의 장소로 이동할 수 있습니다.

이제 주말 이동 계획을 세우면서, $Q$개의 장소 쌍에 대해 적어 둔 경로만 이용해 두 장소 사이를 가장 빠르게 오가는 방법을 알아내야 합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 장소의 수이자 경로의 수인 정수 $N$ ($3 \le N \le 100{,}000$)이 주어집니다.

다음 $N$개의 줄에는 각각 세 정수 $u$, $v$, $w$ ($1 \le w \le 1{,}000$)가 주어지며, 이는 장소 $u$와 $v$(0번부터 시작) 사이를 양방향으로 잇는 경로이고 이동에 $w$의 시간이 걸린다는 뜻입니다.

그다음 줄에는 질의의 수인 정수 $Q$ ($1 \le Q \le 10{,}000$)가 주어집니다.

이어지는 $Q$개의 줄에는 각각 두 정수 $u$, $v$가 주어지며, 장소 $u$에서 $v$까지 가는 최소 시간을 구해야 합니다.

입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 $Q$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째로 질의된 장소 쌍 $u$, $v$ 사이를 이동하는 최소 시간을 정수 하나로 출력합니다.