バレンタインに Farmer John は牛舎でチョコを配り、$B$ 頭の雄牛（$1 \le B \le 25,000$）は好きな雌牛に贈りたいです。

各牛は $N$ 牧草地（$2B \le N \le 50,000$、番号 $1..N$）で1頭ずつ食べ、$M$ 双方向道（$N-1 \le M \le 100,000$）が様々な長さで結びます。同じ2地間に複数の道もあります。道 $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経路）で牛舎へ、さらに $2+1$ で $[3]$、$[4]$ へ贈り、計6。

• 5の牛は4まで3、さらに3、1へ、計 $3+2+1=6$ で贈ります。

• 3の牛は1の牛舎へ距離1、さらに6へ9、計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