SP27340 AR2015PC - Terrorists

天哪！到处都是恐怖分子！在看了几篇关于我附近恐怖袭击的新闻报道后，我大声惊呼。感觉待在家里并不是最佳选择。 我去警察局询问是否可以协助他们防止这些事件发生。警察给了我一些关于恐怖分子行动计划的信息。于是，我躺在床上思考如何利用这些信息。这就是我来找你的原因。 我们的社区可以用交叉路口和道路来描述。恐怖分子通常会在某个交叉路口集合，然后前往另一个交叉路口实施不法行为。我们已知的信息包括他们的集合地点和目标地点。不幸的是，我们无法知道这些计划的具体时间，而最近警力也十分有限。因此，警察无法对所有行动部署有效的防御措施。他们唯一可以做的，是在所有集合点安装监控摄像头。一旦检测到集合，就派警察去集合的目的地抓捕恐怖分子。然而由于警察在路上花费了太多时间，因此很难见效。 恐怖分子很聪明，总是选择交叉路口间的最短路径，而警察则需要我们的帮助。对于每个恐怖分子计划，警察希望我们计算集合地点与目标地点之间的最短距离。如果这个距离太短，他们将选择不浪费人力。

输入的第一行包含一个整数 $T$，代表测试数据的组数 $(1 \le T \le 5)$。 每组测试数据由多行构成。第一行包含三个整数 $N, M, Q$，分别表示交叉路口数量、道路数量和恐怖分子计划的数量。 $1 \le N \le 100\,000, N - 1 \le M \le N + 50, 1 \le Q \le 50\,000$。 紧接着的 $M$ 行用三个整数 $U, V, D$ 描述道路。$U_i$ 和 $V_i$ 表示第 $i$ 条道路的两个端点，$D_i$ 表示该道路的长度。 $1 \le U_i, V_i \le N, 1 \le D_i \le 10\,000$。一对交叉路口之间可能有多条道路。 最后的 $Q$ 行是恐怖活动计划。每个计划 $j$ 由两个整数 $S_j$ 和 $E_j$ 描述，分别表示集合点和目的地。 $1 \le S_j, E_j \le N$。

对于每组测试数据，首先输出 `Case x:`，其中 $x$ 为从 $1$ 开始的测试数据编号，然后接下来输出 $Q$ 行。针对每个恐怖活动计划，输出集合点和目的地之间的最短距离。 **本翻译由 AI 自动生成**