발타자르

발타자르는 휴가를 떠나기로 했다. 지금 그는 발타자르그라드에 있고, 프리모슈텐으로 가려고 한다. 가는 길에는 여러 도시를 지나야 한다. 도시는 $n$개이고, 양방향 도로 $m$개로 연결되어 있다. 발타자르그라드는 1번 도시이고, 프리모슈텐은 $n$번 도시이다.

발타자르는 목적지까지 가는 길을 정확히 모르기 때문에 GPS를 사용한다. GPS는 가장 짧은 경로로 안내한다.

발타자르는 여행을 좋아해서, 자신이 지나가지 않는 도로라도 아무 도로에나 마법 물약을 부을 수 있다. 물약을 부은 도로의 길이는 $2$ 킬로미터 늘어난다. 마법 물약은 한 도로에만 부을 수 있다.

발타자르는 정오 전에 프리모슈텐의 호텔 Zora에 체크인해야 하므로, 최단 경로가 너무 많이 늘어나면 곤란하다. 발타자르그라드에서 프리모슈텐까지의 최단 거리가 정확히 $1$ 킬로미터만 늘어나도록 물약을 부을 수 있는 도로의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 10\,000$). 각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($2 \le n \le 300\,000$, $1 \le m \le \min(300\,000, \frac{n(n-1)}{2})$).

이어지는 $m$개의 줄에는 정수 $a_i$, $b_i$, $w_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le w_i \le 10^9$). 이는 도시 $a_i$와 $b_i$를 잇는 길이 $w_i$의 도로가 있다는 뜻이다. 두 도시 사이에는 도로가 최대 한 개만 있다.

모든 도시는 서로 연결되어 있다. 모든 테스트 케이스에 대해 $n$의 합은 $300\,000$을 넘지 않고, $m$의 합도 $300\,000$을 넘지 않는다.

첫 줄에 발타자르가 마법 물약을 부을 수 있는 도로의 개수 $c$를 출력한다. 둘째 줄에는 그 도로의 번호를 오름차순으로 $c$개 출력한다.

그림에 도시와 도로가 나와 있다. 도로 2 (도시 1과 3 사이) 또는 도로 4 (도시 3과 5 사이)에 물약을 부으면, 도시 1과 도시 $n$ 사이의 최단 거리가 1 늘어난다.