테러리스트

동네는 교차로와 도로로 나타낼 수 있다. 테러리스트는 범행을 저지르기 전에 한 교차로에 모였다가 다른 교차로로 이동한다. 경찰이 확보한 정보에는 집결 교차로와 목적지 교차로가 적혀 있지만, 언제 움직이는지는 적혀 있지 않다.

인력이 부족한 경찰은 모든 범행을 현장에서 막지 못한다. 대신 집결 교차로마다 감시 카메라를 설치해 두고, 집결이 포착되면 그 계획의 목적지로 출동한다. 테러리스트는 교차로 사이를 언제나 최단 경로로 이동한다.

계획마다 집결 교차로와 목적지 교차로 사이의 최단 거리를 구하라.

첫째 줄에 테스트 세트의 개수 $T$가 주어진다. ($1 \le T \le 5$)

각 테스트 세트의 첫째 줄에는 교차로의 수 $N$, 도로의 수 $M$, 테러 계획의 수 $Q$가 순서대로 주어진다. ($1 \le N \le 100000$, $N - 1 \le M \le N + 50$, $1 \le Q \le 50000$)

다음 $M$개 줄에는 도로 하나의 정보가 세 정수 $U$, $V$, $D$로 주어진다. $U$와 $V$는 그 도로가 잇는 두 교차로이고, $D$는 도로의 길이다. ($1 \le U, V \le N$, $1 \le D \le 10000$) 두 교차로를 잇는 도로는 여러 개일 수 있고, $U$와 $V$가 같은 도로도 있을 수 있다. 모든 도로는 양방향이며, 어느 교차로에서든 나머지 모든 교차로로 갈 수 있다.

다음 $Q$개 줄에는 테러 계획 하나의 정보가 두 정수 $S$, $E$로 주어진다. $S$는 집결 교차로, $E$는 목적지 교차로다. ($1 \le S, E \le N$)

각 테스트 세트마다 먼저 Case x:를 출력한다. $x$는 1부터 시작하는 테스트 세트 번호다. 그 다음 $Q$개 줄에 각 테러 계획의 집결 교차로와 목적지 교차로 사이의 최단 거리를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.