题目描述

小明喜欢观景，于是今天他来到了蓝桥公园。

已知公园有 N 个景点，景点和景点之间一共有 M条道路。小明有 Q个观景计划，每个计划包含一个起点 st和一个终点 ed，表示他想从 stst 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入描述

输入第一行包含三个正整数 N,M,Q

第 2 到 M + 1 行每行包含三个正整数 u,v,w表示 vu↔v 之间存在一条距离为 w 的路。

第 M+2 到 M + Q-1 行每行包含两个正整数 st,ed，其含义如题所述。

输出描述

输出共 Q 行，对应输入数据中的查询。

若无法从 st 到达 eded 则输出 −1。

输入输出样例

示例 1

输入

3 3 3 

1 2 1 

1 3 5

2 3 2 

1 2 1 

3 2 3

输出

1 

3 

2

运行限制

语言 最大运行时间 最大运行内存

C++          1s           256M

 C               1s           256M

 Java           3s          256M 

 Python3      50s      256M

JAVA：

C/C++：