Problem G: 多源最短路径

这里有一张包含 n 个点 m 条边的无向图，请你求出图上任意两点之间的最短路径

第 1 行有三个正整数 n(2 <= n <= 100), m(2 <= m <= n*n), k(1 <= k <= 1000)，表示这张图有 n 个点、m 条边，以及接下来有 k 次询问;

第 2 行到第 m+1 行每行有三个正整数 x, y(1 <= x, y <= n), v(0 <= v <= 100), 表示有一条从 x 到 y 的边，这条边的权值是 v;

第 m+2 行到第 m+k+1 行每行有两个正整数 x 和 y，表示题目询问从 x 到 y 的最短路径。

保证这张图上没有重边和自环，保证每次询问的两点都存在。

对于每次询问，输出一行，每行有一个整数表示求得的最短路径。如果两点直接不存在路径则输出 -1

4 6 3
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
2 3
1 3
2 4

2
4
1