题目描述

校园里有 $n$ 栋建筑，编号为 $1$ 到 $n$。建筑之间有 $m$ 条双向步道，每条步道有一个非负整数通行时间。

服务台收到 $q$ 次独立询问，每次给出两栋建筑 $a,b$，需要回答从 $a$ 到 $b$ 的最短通行时间。途中可以经过其他建筑，进入建筑或换用步道不额外耗时。整个询问过程中，步道与通行时间均不改变。

如果两栋建筑之间无法通行，输出 $-1$；如果起终点是同一栋建筑，输出 $0$。

输入格式

第一行三个整数 $n,m,q$，表示建筑数、步道数和询问数。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条连接 $u,v$ 的双向步道，通行时间为 $w$。

接下来 $q$ 行，每行两个整数 $a,b$，表示一次询问。

输出格式

按输入顺序输出 $q$ 行，每行一个整数，表示对应询问的最短通行时间。

样例 1

4 4 4
1 2 4
2 3 3
1 3 10
3 4 2
1 3
4 1
2 4
3 3

7
9
5
0

样例 2

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

-1
0
5

样例解释

样例1：从1到3经过2耗时为4+3=7；从4到1沿4→3→2→1耗时为2+3+4=9；从2到4耗时为3+2=5；从3到自身耗时为0。

样例2：3号建筑与其余建筑不连通，1到3输出-1；3到自身输出0；步道双向通行，2到1耗时为5。

数据范围与约定

全部数据满足：$1\le n\le 300$，$0\le m\le 100000$，$1\le q\le 100000$；$1\le u,v,a,b\le n$，$u\ne v$，$0\le w\le 10^9$。

允许两栋建筑之间存在多条步道，允许零耗时步道；校园不保证连通，询问允许重复，也允许 $a=b$。时间均为整数，答案可能超过32位有符号整数范围。

时间限制：1000ms；内存限制：256m。