题目描述

公司 G 有一个主园区，包含 $N$ 个办公室（编号从 $0$ 到 $N-1$）和 $M$ 条双向道路（编号从 $0$ 到 $M-1$）。第 $i$ 条道路连接一对办公室 ($U_i$, $V_i$)，在这条道路上行驶（任一方向）需要花费 $C_i$ 分钟。

两个办公室 $X$ 与 $Y$ 之间的一条路径是从 $X$ 开始、到 $Y$ 结束的一系列道路。沿某条路径行驶所花费的时间是该路径上各条道路所需时间之和。（数据保证任意两个办公室之间至少存在一条路径。）

公司 G 专精于高效的交通解决方案，但 CEO 刚刚意识到，令人尴尬的是，公司自身的道路网络可能并非最优！她想知道园区中哪些道路是低效的。一条道路是低效的，当且仅当它不被包含在任何两个办公室之间的任何最短路径中。

给定办公室和道路构成的图，你能否帮助 CEO 找出所有低效的道路？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一行包含两个整数 $N$ 和 $M$ 开始，表示办公室和道路的数量。紧接着是 $M$ 行，每行包含三个整数 $U_i$、$V_i$ 和 $C_i$，表示第 $i$ 条道路连接办公室 $U_i$ 和办公室 $V_i$，在其上行驶需要 $C_i$ 分钟。

输出格式

对于每个测试用例，输出一行形如 Case #x: 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后按递增顺序依次输出所有低效道路的编号，每个编号占一行。（注意：道路 $0$ 指测试用例中列出的第一条道路，道路 $1$ 指第二条，依此类推。）

2
3 3
0 1 10
1 2 3
2 0 3
3 3
0 1 10
1 2 3
2 1 3

Case #1: 
0
Case #2:

提示

限制

$0 < C_i \le 1000000$。

小数据集（测试集 1 - 可见）

$1 \le T \le 10$。

$1 \le N = M \le 100$。

大数据集（测试集 2 - 隐藏）

$1 \le T \le 3$。

$1 \le N \le 100$。

$1 \le M \le 10000$。

翻译由 DeepSeek V4 Pro 完成