题目描述

Company G has a main campus with $N$ offices (numbered from 0 to $N - 1$) and $M$ bidirectional roads (numbered from 0 to $M - 1$). The $i$th road connects a pair of offices ($U_i$, $V_i$), and it takes $C_i$ minutes to travel on it (in either direction).

A path between two offices $X$ and $Y$ is a series of one or more roads that starts at $X$ and ends at $Y$. The time taken to travel a path is the sum of the times needed to travel each of the roads that make up the path. (It's guaranteed that there is at least one path connecting any two offices.)

Company G specializes in efficient transport solutions, but the CEO has just realized that, embarrassingly enough, its own road network may be suboptimal! She wants to know which roads in the campus are inefficient. A road is inefficient if and only if it is not included in any shortest paths between any offices.

Given the graph of offices and roads, can you help the CEO find all of the inefficient roads?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each case begins with one line with two integers $N$ and $M$, indicating the number of offices and roads. This is followed by $M$ lines containing three integers each: $U_i$, $V_i$ and $C_i$, indicating the $i$th road is between office $U_i$ and office $V_i$, and it takes $C_i$ minutes to travel on it.

输出格式

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output the road numbers of all of the inefficient roads, in increasing order, each on its own line. (Note that road 0 refers to the first road listed in a test case, road 1 refers to the second road, etc.)

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:

提示

Limits

$0 < C_i \le 1000000$.

Small dataset (Test Set 1 - Visible)

$1 \le T \le 10$.

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

Large dataset (Test Set 2 - Hidden)

$1 \le T \le 3$.

$1 \le N \le 100$.

$1 \le M \le 10000$.