gCampus (작은 입력)

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

서로 다른 두 사무실 $X$와 $Y$를 잇는 경로는 $X$에서 시작해 $Y$에서 끝나는, 도로 하나 이상을 이어 붙인 열이다. 경로를 지나는 데 걸리는 시간은 그 경로를 이루는 도로의 시간을 모두 더한 값이다. 어떤 두 사무실 사이에도 경로가 적어도 하나 있다. 두 사무실 사이의 최단 경로는 두 사무실을 잇는 경로 중 걸리는 시간이 가장 짧은 경로이고, 여러 개일 수 있다.

G 회사는 효율적인 운송을 파는 회사인데, 정작 자기 캠퍼스의 도로망이 최적이 아닐 수도 있다는 사실을 대표가 알아차렸다. 대표는 캠퍼스에서 비효율적인 도로가 무엇인지 알고 싶어 한다. 어떤 도로가 비효율적이라는 것은, 서로 다른 두 사무실을 잇는 어떤 최단 경로에도 그 도로가 들어가지 않는다는 뜻이다.

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

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

같은 두 사무실을 잇는 도로가 여러 개일 수 있고, 양 끝이 같은 사무실인 도로도 있을 수 있다.

제한

• $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$

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