题目描述
FJ 有 B 头奶牛 (1≤B≤25000),有 N(2×B≤N≤50000) 个农场,编号 1 到 N,有 M(N−1≤M≤100000) 条双向边,第 i 条边连接农场 Ri 和 Si(1≤Ri≤N,1≤Si≤N),该边的长度是 Li(1≤Li≤2000)。居住在农场 Pi 的奶牛 A (1≤Pi≤N),想送一份新年礼物给居住在农场 Qi(1≤Qi≤N) 的奶牛 B,但是奶牛 A 必须先到 FJ(居住在编号 1 的农场)那里取礼物,然后再送给奶牛 B。你的任务是:奶牛 A 至少需要走多远的路程?
输入格式
- 第一行三个整数 N,M,B。
- 第 2 至 M+1 行,每行 3 个整数 Ri,Si,Li。
- 第 M+2 至 M+B+1 行,进行 B 次询问,每行 2 个整数 Pi,Qi。
输出格式
每次询问输出一个整数,即答案。
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