图上最短路V

题目描述

给定一张由 $n$ 个点和 $m$ 条边组成的带权无向图，并且给出 $T$ 组询问，每次询问图上任意两点 $S$ 和 $T$ 的最短路，如果不可达，请输出-1。

输入格式

第一行为三个整数 $n,m,T$，分别表示询问点数，边数和询问次数。 接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示存在一条连接 $u$ 和 $v$，且长度为 $w$ 的边。

数据范围： $1 \le n \le 200$ $1 \le m, T \le 200000$ $1 \le u, v \le n$ $1 \le w \le 10^9$

输出格式

对于每组询问，给出答案。

样例 #1

样例输入 #1

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

样例输出 #1

5
4
2