Problem #3067 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

唐门兄弟和肖打赌：

肖：我们玩躲猫猫，保证你 5 小时内找不到我！

唐：在飞车上没人比得过我！

好戏上演，唐门兄弟再次表演空降，假设飞机可以一开始把他们送到任何一个城市（送到城市后，将开始赛车的追逐），这时比赛开始，在鹰眼的帮助下可以迅速知道肖所在的城市（但是在部署人员的时候并不知道），我们必须保证能够在最短时间内到达肖所在的城市，将其抓住。

第一行为测试数据组数 $T$ 。

对每一组数据，输入三个整数 $N$ ( $1 \leq N \leq 50$ ), $M$ ( $0 \leq M \leq \frac{N (N - 1)}{2}$ ), $K$ ( $1 \leq K \leq 10$ ) 分别表示 $N$ 座城市， $M$ 条路， $K$ 个人来追踪肖。

接下去 $M$ 行，每一行三个整数 $u, v, w$ ( $1 \leq u \leq N, 1 \leq v \leq N, 1 \leq w \leq 10^{6}$ )， $u, v$ 分别表示城市编号， $w$ 表示从城市 $u$ 和 $v$ 需要 $w$ 小时的路程。

对于每组数据，先输出 Case #X:，其中 X 表示第几组数据，再输出抓住肖的最短时间，假如无法抓住肖，输出 $- 1$ 。

Input

Output

Case #1:3
Case #2:2
Case #3:-1

1 人解决，4 人已尝试。

1 份提交通过，共有 5 份提交。

9.9 EMB 奖励。

创建: 9 年，11 月前.

修改: 7 年，5 月前.

最后提交: 1 月，1 周前.

3067. Fast & Furious 7