#2488. 城市之间的联系

城市之间的联系

Description

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

Format

Input

输入包含多个测试用例。每个用例的第11行都包含33个整数 nmc2n100000m<100001c1000000n、m、c (2≤n ≤10000,0≤m <10000,1≤c ≤1000000)nn 表示 城市数,编号为1n1~n 。接下来的mm 行,每行都包含33个整数ijki、j 和k ,表示城市ii 和城市jj 之间的道路,长度为kk 。最后cc 行,每行都包含 iji、j 两个整数,表示查询城市ii 和城市jj 之间的最短距离。

Output

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

Samples

5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5
Not connected
6

来源

HDU2874