题目描述

译自 COCI 2022/2023 Contest #3 T3「Baltazar」

Baltazar 准备去度假。目前，他在 Baltazargrad，想去 Primošten 旅行。为了到达目的地，他需要经过许多城市。共有 $n$ 个城市，有 $m$ 条双向道路将它们连通。Baltazargrad 编号为 $1$，Primošten 编号为 $n$。

Baltazar 不确定 Baltazargrad 到 Primošten 的路线，所以他会使用 GPS。GPS 会引导他走到目的地的最短路线。

但是 Baltazar 十分喜欢旅行，并且他可以在任何道路（甚至是他不会经过的道路）上倒一种魔法药水，然后这条道路的长度就会增加 $\mathbf{2}$ 公里。他只能在一条道路上倒魔法药水。

很快他意识到他必须在正午之前入住 Primošten 的 Zora 酒店，所以他不能让最短路径的长度增加太多。现在，他想知道他可以在多少条路上倒魔法药水，使得 Baltazargrad 和 Primošten 之间的最短路径长度恰好增加 $\mathbf{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\cdot (n-1)}{2}))$，表示城市个数和道路条数。

接下来 $m$ 行，每行三个整数 $a_i,b_i,w_i\ (1\le a_i,b_i\le n,a_i\neq b_i,1\le w_i\le 10^9)$，表示有一条连接城市 $a_i$ 和 $b_i$ 的路，长度为 $w_i$。在任意两个城市之间，最多只有一条路连接它们。

所有的城市都是连通的，即，对于任意两个城市，存在一条从其中一个城市到另一个的路径，但不一定是直接到达的。

保证一组数据中所有测试点的 $n$ 总和不超过 $300\ 000$，$m$ 总和不超过 $300\ 000$。

输出格式

第一行输出一个整数 $c$，表示 Baltazar 可以在多少条道路上倒魔法药水。第二行输出 $c$ 个整数，表示这些道路的下标，按编号递增的顺序输出。

3
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 3
5 6 2
6 7
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
1 6 7

2
2 4
0

3
2 4 6

数据范围与提示

详细子任务附加限制及分值如下表所示。