题目描述

给定$n$个点$m$条边的无向图，以及$k$次询问，每次询问你需要回答$x,y$两个点之间的最短路长度，如果两个点不连通，输出-1。

输入格式

第一行输入三个整数$n,m,k$。 接下来$m$行，每行输入三个整数$u,v,w$，表示一条连接$u,v$，长度为$w$的边。 接下来$k$行，每行输入两个整数$x,y$，表示一次询问。

输出格式

输出共$k$行，依次输出每次询问对应的答案。

样例输入 #1

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

样例输出 #1

5
2
1

说明/提示

有$1\leq n\leq 100,0\leq m,k\leq \frac{n(n-1)}{2},1\leq w\leq 10^9$。