希蒙最近经营了菜鸟驿站，现在有B名快递员(1<=B<=25000)需要将快递送到别人家里，因此他们需要先到希蒙所在位置拿取快递，再去送货上门。

目前地图中共$N(2×B<=N<=50000)$个地点，编号$1 至 N$，它们由$M(N-1<=M<=100000)$条双向路连接，第i条路连接点$R_i和S_i(1<=R_i<=N;1<=S_i<=N)$，该路的距离是$L_i(1<=L_i<=2000)$。

居住在地点$P_i$的快递员$A(1<=P_i<=N)$，要送货到$Q_i(1<=Q_i<=N)$的地点，菜鸟驿站所在的位置为点1，现需要计算，这次送货最短距离是多少？

             [4]--3--[5]  
            /  |
           /   |
          4    2         
         /     |              
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

输入格式

第一行有三个整数，分别是: N, M, and B

第2行到第M+1行，每行三个数字，分别是: $R_i, S_i,L_i$

第M+2行到第M+B+1行，每行两个数字: $P_i , Q_i$

输出格式

共B行输出，每行一个整数，分别表示每个循环对应的最小花费

样例 #1

样例输入 #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