好的，这是整理好的题面，不含解题思路，只包含样例解释。

题目描述

Freda 和 rainbow 所在的地方有 $N$ 座房屋、$M$ 条双向光缆。
每条光缆连接两座房屋，传呼机信号只能沿着光缆传递，且信号从光缆一端传到另一端需要花费 $t$ 单位时间。

Freda 要进行 $Q$ 次试验，每次选取两座房屋，想知道信号在这两座房屋之间传递至少需要多长时间。
房屋通过光缆一定连通，且这 $M$ 条光缆属于以下三类连接情况之一（题目会给出符合其中一种的数据）：

• A 类：光缆不形成环，即 $M = N-1$（一棵树）。
• B 类：光缆只形成一个环，即 $M = N$（一棵基环树，只有一个环）。
• C 类：每条光缆仅在一个环中（即该图是仙人掌图，任意两条环不共享边）。

请帮他们计算每次查询的最短时间。

输入格式

第一行三个整数 $N, M, Q$。
接下来 $M$ 行，每行三个整数 $x, y, t$，表示房屋 $x$ 和 $y$ 之间有一条传递时间为 $t$ 的光缆。
最后 $Q$ 行，每行两个整数 $x, y$，表示一次询问。

输出格式

输出 $Q$ 行，每行一个整数，表示对应询问的最短传递时间。

数据范围

• $2 \le N \le 10000$
• $N-1 \le M \le 12000$
• $Q = 10000$
• $1 \le x,y \le N$
• $1 \le t < 32768$

输入样例

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

输出样例

3
1

样例解释

数据说明

$N=5, M=4, Q=2$
光缆（双向）：

1. 1-2 时间 1
2. 1-3 时间 1
3. 2-4 时间 1
4. 2-5 时间 1

这是 A 类（$M=N-1$，树形结构），图如下：

    1
   / \
  2   3
 / \
4   5

询问 1：3 到 5

路径：3→1→2→5，时间 = 1 + 1 + 1 = 3。
没有更短路径（因为树中路径唯一）。

输出 3。

询问 2：2 到 1

路径：2→1，时间 = 1。

输出 1。

最终输出：

3
1