gCampus (Large)

G사의 본사 캠퍼스에는 사무실 $N$개(0번부터 $N-1$번까지)와 양방향 도로 $M$개(0번부터 $M-1$번까지)가 있다. $i$번 도로는 사무실 $U_i$와 사무실 $V_i$를 잇고, 어느 방향으로 지나든 $C_i$분이 걸린다.

사무실 $X$와 사무실 $Y$를 잇는 경로는 $X$에서 시작해 $Y$에서 끝나는, 도로 한 개 이상의 나열이다. 경로를 지나는 데 걸리는 시간은 그 경로를 이루는 도로의 소요 시간을 모두 더한 값이다. 어떤 두 사무실 사이에도 경로가 적어도 하나 있다는 것이 보장된다.

G사는 효율적인 운송을 다루는 회사인데, 정작 자기 캠퍼스의 도로망이 최적이 아닐 수도 있다는 사실을 대표가 방금 깨달았다. 대표는 캠퍼스의 도로 중 어느 것이 비효율적인지 알고 싶어 한다. 어떤 도로가 비효율적이라는 것은, 그 도로가 어느 두 사무실 사이의 어떤 최단 경로에도 들어가지 않는다는 뜻이다.

사무실과 도로로 이루어진 그래프가 주어질 때, 비효율적인 도로를 모두 찾아라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 첫째 줄에는 사무실의 개수 $N$과 도로의 개수 $M$이 주어진다. 다음 $M$개의 줄에는 정수 세 개 $U_i$, $V_i$, $C_i$가 주어진다. $i$번 도로가 사무실 $U_i$와 사무실 $V_i$를 잇고, 지나는 데 $C_i$분이 걸린다는 뜻이다.

제한

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

각 테스트 케이스마다 Case #x:를 한 줄에 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. 그 다음 줄부터 비효율적인 도로의 번호를 증가하는 순서로 한 줄에 하나씩 출력한다. 비효율적인 도로가 없으면 Case #x: 줄만 출력한다. 0번 도로는 그 테스트 케이스에서 첫 번째로 주어진 도로, 1번 도로는 두 번째로 주어진 도로를 가리킨다.