#2125. 最短路

题目描述

给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

输入格式

输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问

输出格式

输出Q行，每行一个整数表示询问的答案

样例

样例输入

9 10 2  

1 2 1  

1 4 1  

3 4 1  

2 3 1  

3 7 1  

7 8 2  

7 9 2  

1 5 3  

1 6 4  

5 6 1  

1 9  

5 7  

样例输出

5  

6  

数据范围与提示

对于100%的数据，N<=10000，Q<=10000