题目描述

有 $n$ 个交通节点和 $m$ 条原有的无向道路，节点编号 $1$ 到 $n$。原有道路通行时间为正整数。可能有不连通的节点。

现有 $q$ 份互相独立的临时通道方案。第 $i$ 份方案给出两个不同的节点 $u_i,v_i$，表示在它们之间额外增设一条通行时间为 $0$ 的无向道路。

对于每份方案，请计算在仅增加这条道路时，从节点 $1$ 到节点 $n$ 的最短通行时间；若仍然无法到达，输出 $-1$。

重要： 每份方案相互独立，计算完一份方案后立即撤销新增道路。即使原图中已有一条连接 $u_i,v_i$ 的道路，也允许新增平行的零时间道路。

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示原有无向道路及通行时间。

接下来 $q$ 行，每行两个整数 $u,v$，表示一份临时通道方案。

输出格式

输出 $q$ 行，每行一个整数，依次回答每份方案。

样例 1

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

0
5
5

数据范围与部分分

保证 $2\le n\le2\times10^5$，$0\le m\le\min(3\times10^5,\frac{n(n-1)}2)$，$1\le q\le2\times10^5$；原图中无自环或重边；$1\le w\le10^9$。每次询问保证 $1\le u,v\le n$ 且 $u\ne v$。

最短路径长度可能超过 32 位有符号整数的上限。