题目描述
小明喜欢观景，于是今天他来到了蓝桥公园。
已知公园有N 个景点，景点和景点之间一共有M 条道路。小明有Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？
输入
输入第一行包含三个正整数 N,M,Q 。
第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。
第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed，其含义如题所述。
1≤N≤400，1≤M≤ N×(N−1)/2 ，Q≤103 ，1≤u,v,st,ed≤n，1≤w≤109。
输出
输出共Q 行，对应输入数据中的查询。
若无法从st 到达 ed 则输出 −1。
3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3