gCampus

G사에는 N개의 사무실(0부터 N - 1까지 번호가 매겨짐)이 있는 본사 캠퍼스와 M개의 양방향 도로(0부터 M - 1까지 번호가 매겨짐)가 있다. i번째 도로는 한 쌍의 사무실($U_{i}$, $V_{i}$)을 연결하며, 이 도로를 이동하는 데에는 (어느 방향이든) $C_{i}$분이 걸린다.

두 사무실 X와 Y 사이의 경로는 X에서 시작해 Y에서 끝나는 하나 이상의 도로로 이루어진 일련의 연결이다. 경로를 이동하는 데 걸리는 시간은 그 경로를 구성하는 각 도로를 이동하는 데 필요한 시간의 합이다. (임의의 두 사무실을 연결하는 경로가 적어도 하나 존재함이 보장된다.)

G사는 효율적인 운송 솔루션을 전문으로 하지만, CEO는 당혹스럽게도 자사의 도로망이 최적이 아닐 수도 있다는 사실을 이제야 깨달았다! 그녀는 캠퍼스의 어떤 도로가 비효율적인지 알고 싶어 한다. 어떤 도로가 임의의 사무실 사이의 어떤 최단 경로에도 포함되지 않을 때, 그리고 그럴 때에만 그 도로는 비효율적이다.

사무실과 도로의 그래프가 주어질 때, CEO가 모든 비효율적인 도로를 찾도록 도울 수 있는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 0 < $C_{i}$ ≤ 1000000.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 10. 1 ≤ N = M ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 3. 1 ≤ N ≤ 100. 1 ≤ M ≤ 10000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 사무실과 도로의 수를 나타내는 두 정수 N과 M이 있는 한 줄로 시작한다. 이어서 각각 세 정수 $U_{i}$, $V_{i}$, $C_{i}$를 포함하는 M개의 줄이 주어진다. 이는 i번째 도로가 사무실 $U_{i}$와 사무실 $V_{i}$ 사이에 있으며, 이 도로를 이동하는 데 $C_{i}$분이 걸린다는 뜻이다.

각 테스트 케이스마다 "Case #x:"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. 그런 다음 모든 비효율적인 도로의 번호를 증가하는 순서로 각각 별도의 줄에 출력한다. (도로 0은 테스트 케이스에서 첫 번째로 나열된 도로를 가리키고, 도로 1은 두 번째로 나열된 도로를 가리키는 식이다.)