题目描述

农场主约翰在谷仓（编号为 $1$）准备了巧克力，打算在情人节分发给奶牛们。农场共有 $N$（$2\times B \le N \le 50000$）个牧场，编号 $1\dots N$，由 $M$（$N-1 \le M \le 10^5$）条双向小路连接，每条小路有长度。两个牧场之间可能有多条小路相连。

第 $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$）。

有 $B$（$1 \le B \le 25000$）头公牛，第 $i$ 头公牛住在牧场 $P_i$（$1 \le P_i \le N$），他想把巧克力送到住在牧场 $Q_i$（$1 \le Q_i \le N$）的母牛手中。公牛必须先从自己的牧场走到谷仓（牧场 $1$），拿到巧克力后再走到母牛所在的牧场。

请帮每头公牛计算从自己的牧场出发，经由谷仓，到达母牛所在牧场的最短路径长度。

输入格式

第 $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$。

输出格式

共 $B$ 行，第 $i$ 行输出一个整数，表示第 $i$ 头公牛需要走的最短距离。

样例

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

6 
6
10