题目背景
翻译自 CSES-1672 题。
题目描述
有 n 个城市和 m 条道路连接它们。每条道路都是双向的，并有一个长度。你的任务是处理 q 个查询，对于每个查询，输出两个给定城市之间的最短路径长度。如果两个城市之间没有路径，则输出 −1。
输入格式
第一行包含三个整数 n,m,q，分别表示城市的数量、道路的数量和查询的数量。
接下来 m 行，每行包含三个整数 a,b,c，表示城市 a 和城市 b 之间有一条长度为 c 的双向道路。
接下来 q 行，每行包含两个整数 a,b，表示一次查询，你需要输出城市 a 和城市 b 之间的最短路径长度。
输出格式
对于每个查询，输出一行一个整数，即最短路径长度。若两城市不连通，输出 −1。
样例
4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2
5
5
8
-1
3
样例解释
道路网络：1↔2 (5)，1↔3 (9)，2↔3 (3)。
- 查询 1→2：最短路径为 1→2，长度 5。
- 查询 2→1：最短路径为 2→1，长度 5。
- 查询 1→3：最短路径为 1→2→3，长度 5+3=8。
- 查询 1→4：城市 4 与任何城市都没有道路，不连通，输出 −1。
- 查询 3→2：最短路径为 3→2，长度 3。
数据范围
- 1≤n≤500
- 1≤m≤n2
- 1≤q≤105
- 1≤a,b≤n
- 1≤c≤109
