情人节 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