题目描述

FJ 有 $B$ 头奶牛 $(1\le B\le 25000)$，有 $N(2\times B\le N\le 50000)$ 个农场，编号 $1$ 到 $N$，有 $M(N-1\le M\le 100000)$ 条双向边，第 $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)$。居住在农场 $P_i$ 的奶牛 A $(1\le P_i\le N)$，想送一份新年礼物给居住在农场 $Q_i(1\le Q_i\le N)$ 的奶牛 B，但是奶牛 A 必须先到 FJ（居住在编号 $1$ 的农场）那里取礼物，然后再送给奶牛 B。你的任务是：奶牛 A 至少需要走多远的路程？

输入格式

• 第一行三个整数 $N,M,B$。

• 第 $2$ 至 $M+1$ 行，每行 $3$ 个整数 $R_i,S_i,L_i$。

• 第 $M+2$ 至 $M+B+1$ 行，进行 $B$ 次询问，每行 $2$ 个整数 $P_i ,Q_i$。

输出格式

每次询问输出一个整数，即答案。

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