战后有很多城市被严重破坏，我们需要重建城市。然而，有些建设材料只能在某些地方产生。因此，我们必须通过城市交通，来运送这些材料的城市。由于大部分道路已经在战争期间完全遭到破坏，可能有两个城市之间没有道路。当然在运输线中，更不可能存在圈。 现在，你的任务来了。给你战后的道路情况，我们想知道，两个城市之间是否存在道路，如果存在，输出这两个城市之间的最短路径长度。

第一行一个整数 $T$ $(T = 1)$，表示测试数据组数。 每组测试数据第一行包含三个整数 $N, M, C$ $(2 \le N \le 10\,000, 0 \le M \lt 10\,000, 1 \le C \le 1\,000\,000)$ 共有 $N$ 个城市，现存 $M$ 条边，共有 $C$ 对运输需求。 接下来 $M$ 行，每行三个整数 $A, B, D$ $(1 \le A, B \le N,A \ne B, 1 \le D \le 10\,000)$ 表示从 $A$ 到 $B$ 有一条直接的公路，且距离为 $D$。 最后 $C$ 行，每行两个整数 $S, T$ $(1 \le S,T \le N, S \ne T)$，即询问从 $S$ 到 $T$ 的最短路径长度。

共 $T$ 行，否存在从 $S$ 到 $T$ 的路径，则输出最短路径，否则输出 `Not connected`。