A 市有 N 个社区（编号 1 \sim N），由 M 条双向的道路连接这些社区。
该市共有 B 个快递员，每个快递员都有一个快递运送任务，第 i 个快递员，目前位于位置为 P_i 的社区，他需要去编号为 1 的社区（该社区设有快递中转站）领取快递包裹，再将该包裹送到编号为 Q_i 的社区。
请编程计算出对于每个快递员完成快递任务，需要走到的最短路是多少？
第 1 行读入 3 个整数 N,M,B。
接下来 M 行，每行读入 3 个整数 u,v,len，表示编号为 u,v 的社区之间有一条长度为 len 的双向道路。
接下来 B 行，每行有两个整数 P_i,Q_i，表示快递员的位置和他要去的社区编号。
输出 B 行，分别针对 B 个快递任务，计算出最短路。
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
对于 100\% 的数据，1 \le B \le 25000，2 \times B \le N \le 50000，N-1 \le M \le 100000，1 \le u,v \le N，1 \le len \le 2000，1 \le P_i,Q_i \le N。
测试数据确保每个快递员都一定有边能够使其从 P_i 到 1 ，再到 Q_i 。
东方博宜OJ