P10932 Freda的传呼机

为了随时与 rainbow 快速交流，Freda 制造了两部传呼机。 Freda 和 rainbow 所在的地方有 $N$ 座房屋、$M$ 条双向光缆。 每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费 $t$ 单位时间。 现在 Freda 要进行 $Q$ 次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。 $N$ 座房屋通过光缆一定是连通的，并且这 $M$ 条光缆有以下三类连接情况： * $A$：光缆不形成环，也就是光缆仅有 $N-1$ 条。 * $B$：光缆只形成一个环，也就是光缆仅有 $N$ 条。 * $C$：每条光缆仅在一个环中。 请你帮帮他们。

第一行包含三个用空格隔开的整数，$N、M$ 和 $Q$。 接下来 $M$ 行每行三个整数 $x、y、t$，表示房屋 $x$ 和 $y$ 之间有一条传递时间为 $t$ 的光缆。 最后 $Q$ 行每行两个整数 $x、y$，表示 Freda 想知道在 $x$ 和 $y$ 之间传呼最少需要多长时间。

输出 $Q$ 行，每行一个整数，表示 Freda 每次试验的结果。

数据保证，$2 \le N \le 10000$，$N-1 \le M \le 12000$，$Q = 10000$，$1 \le x,y \le N$，$1 \le t < 32768$。