题目描述
FJ 有 \( B \) 头奶牛 (\( 1 \le B \le 25000 \)),有 \( N \) 个农场,编号 \( 1 \) 到 \( N \) (\( 2 \times B \le N \le 50000 \)),有 \( 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 \) 的奶牛 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$。