情人節 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 路，3 公牛在 2、3、5，想贈送巧克力：

                      *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$ 行用空格分隔整數 $R_i$、$S_i$、$L_i$ 描述路 $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