gCampus (Small)

The main campus of company G has $N$ offices, numbered 0 to $N-1$, and $M$ bidirectional roads, numbered 0 to $M-1$. Road $i$ joins offices $U_i$ and $V_i$, and travelling along it takes $C_i$ minutes in either direction.

A path between two different offices $X$ and $Y$ is a sequence of one or more roads that starts at $X$ and ends at $Y$. The time of a path is the sum of the times of the roads that make it up. At least one path exists between every pair of offices. A shortest path between two offices is a path of minimum total time, and there can be several of them.

Company G sells efficient transport, and the CEO has just realised that her own road network may not be optimal. She wants to know which roads on the campus are inefficient. A road is inefficient when no shortest path between any two different offices contains it.

Given the offices and the roads, find every inefficient road.

The first line contains the number of test cases $T$. Each test case begins with a line holding two integers $N$ and $M$, the number of offices and the number of roads. $M$ lines follow, each with three integers $U_i$, $V_i$ and $C_i$: road $i$ joins offices $U_i$ and $V_i$ and takes $C_i$ minutes.

Several roads may join the same pair of offices, and a road may have the same office at both ends.

Limits

• $1 \le T \le 10$
• $1 \le N = M \le 100$
• $0 < C_i \le 1000000$
• $0 \le U_i, V_i \le N-1$

For each test case, print one line with "Case #x:", where $x$ is the test case number starting from 1. Then print the numbers of all inefficient roads in increasing order, one per line. If there is no inefficient road, print only the "Case #x:" line. Road 0 is the first road listed in that test case.