Description

由于大部分道路在战争期间已被完全摧 毁，所以两个城市之间可能没有路径，也没有环。已知道路状况，想知 道任意两个城市之间是否存在路径。若答案是肯定的，则输出它们之间 的最短距离。

Format

Input

输入包含多个测试用例。每个用例的第$1$行都包含$3$个整数 $n、m、c （2≤n ≤10000，0≤m <10000，1≤c ≤1000000）$。$n$ 表示 城市数，编号为$1～n$ 。接下来的$m$行，每行都包含$3$个整数$i、j 和k$ ，表示城市$i$ 和城市$j$ 之间的道路，长度为$k$ 。最后$c$ 行，每行都包含 $i、j$ 两个整数，表示查询城市$i$和城市$j$之间的最短距离。

Output

对每个查询，若两个城市之间没有路径，则输出“Not connected”，否则输出它们之间的最短距离。

Samples

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

Not connected
6

来源

HDU2874