초콜릿 선물하기

문제

발렌타인데이를 맞아 농부가 헛간에서 초콜릿을 나눠주고 있습니다. $B$ ($1 \le B \le 25000$)마리의 수소가 각자 초콜릿을 선물하고 싶은 특별한 암소를 마음에 두고 있습니다.

모든 수소와 암소는 농장의 목초지 $N$ ($2B \le N \le 50000$)개 중 하나에서 홀로 풀을 뜯고 있습니다. 목초지는 $1$번부터 $N$번까지 번호가 매겨져 있으며, 길이가 다양한 양방향 소길 $M$ ($N-1 \le M \le 100000$)개로 연결되어 있습니다. 두 목초지가 여러 개의 소길로 직접 연결되어 있을 수도 있습니다. $i$번 소길은 목초지 $R_i$와 $S_i$ ($1 \le R_i \le N$; $1 \le S_i \le N$)를 잇고 길이는 $L_i$ ($1 \le L_i \le 2000$)입니다.

$i$번 수소는 목초지 $P_i$ ($1 \le P_i \le N$)에 살고 있으며, 목초지 $Q_i$ ($1 \le Q_i \le N$)에 있는 암소에게 초콜릿을 선물하고 싶어 합니다.

각 수소가 자신의 목초지에서 헛간(목초지 $1$번에 위치)까지 갔다가, 다시 자신이 좋아하는 암소가 있는 목초지까지 가는 가장 짧은 경로를 찾도록 도와주세요. 헛간은 (직접이든 다른 목초지와 소길을 거치든) 모든 목초지와 연결되어 있습니다.

예를 들어, 목초지 6개, 소길 7개, 그리고 (목초지 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번의 수소는 목초지 4번까지(거리 3) 간 다음, 목초지 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$번의 암소에게 전하기 위해 이동해야 하는 최소 총 거리입니다.