gCampus (Large)

Company G has a main campus with $N$ offices, numbered 0 to $N-1$, and $M$ bidirectional roads, numbered 0 to $M-1$. Road $i$ connects office $U_i$ and office $V_i$, and travelling on it takes $C_i$ minutes in either direction.

A path between office $X$ and office $Y$ is a sequence 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 of the roads that make it up. Every pair of offices is connected by at least one path.

Company G works on efficient transport, but the CEO has just realized that the company's own road network may be suboptimal. She wants to know which roads on the campus are inefficient. A road is inefficient if and only if it lies on no shortest path between any two offices.

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

The first line of the input contains the number of test cases, $T$. $T$ test cases follow. Each case begins with a line holding two integers $N$ and $M$, the number of offices and the number of roads. Then follow $M$ lines with three integers each, $U_i$, $V_i$ and $C_i$, meaning that road $i$ runs between office $U_i$ and office $V_i$ and takes $C_i$ minutes to travel.

Limits

• $0 < C_i \le 1000000$
• $1 \le T \le 3$
• $1 \le N \le 100$
• $1 \le M \le 10000$

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