밸런타인데이에 Farmer John은 외양간에서 초콜릿을 나눠 줍니다. $B$마리 수소($1 \le B \le 25,000$)에게는 초콜릿을 주고 싶은 특별한 암소가 있습니다.

각 소는 $N$개 목초지($2B \le N \le 50,000$), 번호 $1..N$ 중 하나에서 혼자 풀을 먹습니다. 길이가 다양한 $M$개 양방향 길($N-1 \le M \le 100,000$)이 연결하며, 두 목초지 사이에 여러 길이 직접 연결될 수도 있습니다. 길 $i$는 $R_i$, $S_i$($1 \le R_i \le N; 1 \le S_i \le N$)를 연결하며 길이는 $L_i$($1 \le L_i \le 2,000$)입니다.

수소 $i$는 $P_i$($1 \le P_i \le N$)에 살며 $Q_i$($1 \le Q_i \le N$)의 암소에게 선물하려 합니다.

현재 목초지에서 외양간(목초지 1)을 거쳐 특별한 암소의 목초지로 가는 최단 경로를 구하세요. 외양간에서는 다른 길과 목초지를 거쳐 모든 목초지에 도달할 수 있습니다.

목초지 6개, 길 6개, 2, 3, 5에 있는 수소 3마리가 연인에게 초콜릿을 주려는 예입니다.

                      *1  <-- 수소는 목초지 1의 암소에게 초콜릿을 주려 함
             [4]--3--[5]  <-- [5]는 목초지 번호
            /  |
           /   |
          4    2          <-- 2는 길의 길이
         /     |               [3]과 [4] 사이
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• 2의 수소는 거리 3(두 경로)으로 외양간에 가고, $2+1$을 더 가 $[3]$, $[4]$에서 선물하므로 총 6입니다.

• 5의 수소는 거리 3으로 4에 간 뒤 3과 1로 가서 총 $3+2+1=6$으로 선물합니다.

• 3의 수소는 거리 1로 외양간 1에 가고 초콜릿을 들고 거리 9로 6에 가므로 총 10입니다.

입력

• 1번 줄: 공백으로 구분한 정수 $N$, $M$, $B$.

• $2..M+1$번 줄: $i+1$번 줄은 길 $i$를 공백으로 구분한 정수 $R_i$, $S_i$, $L_i$로 설명합니다.

• $M+2..M+B+1$번 줄: $M+i+1$번 줄에 공백으로 구분한 정수 $P_i$, $Q_i$.

출력

• $1..B$번 줄: $i$번 줄에 정수 하나, $P_i$의 수소가 외양간에서 초콜릿을 받아 $Q_i$의 꿈의 암소에게 주기 위한 최단 거리.

예제

입력 1

6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2 4
5 1
3 6

출력 1

6
6
10

문제 작성: Brian Hamrick, 2010