题目描述

小码君又要去上学了，不过这次他可以自由选择从哪个地方出发，以及到哪个学校上学，你来帮助他计算一下上学的最短距离吧

输入格式

第一行，包含3个参数n,m,k，表示地图中有n个地点，m条道路，k次询问
接下来m行输入，每行三个整数a,b,c，表示从a点出发到b点距离为c，注意，因为城市交通规划，此道路全为单行道
最后k行输入，每行两个整数x，y，表示需要计算，从x点出发，到达y点的最短距离

输出格式

对于每个询问，都需要给出x点到y点的最短距离，如果无法到达，输出-1，并且每个输出间隔一行

样例

样例输出

5 10 5
3 2 4
5 4 5
1 3 3
5 1 5
5 2 8
4 2 9
2 3 10
4 3 2
3 5 8
2 1 6
1 4
4 3
5 1
2 5
3 1

样例输出

16
2
5
17
10

数据范围与提示

1<=n,m<=100
1<=k<=50