题目描述

Baltazar 准备去度假。他现在在 Baltazargrad，正想去 Primosten 旅游。为了抵达那里，他需要穿过许多个城市。一共有 $n$ 个城市，被 $m$ 条双向道路所联接。Baltazargrad 编号为 $1$，Primosten 编号为 $n$。

Baltazar 不确定从 Baltazargrad 去 Primosten 的路线，所以他将会使用 GPS，这会指引他以最短路线抵达。

但 Blatazar 真的很爱旅游，而且他可以将魔法药水使用在任何一条路上（即使他没有经过），从而将路的长度增长 $2$ 千米。但他仅能使用一次药水。

不久他意识到，他必须在中午之前在 Primosten 的 Zora 旅馆入住。所以他不能过分增加最短路的总长度。他现在想知道，一共有多少条路可以让他使用药水，使得最短路的长度恰好增加 $1$ 千米。

输入格式

多组数据。

第一行一个整数 $t$，表示数据组数。

接下来对于每组数据，第一行两个整数 $n,m$，分别表示城市的数量和城市之间道路的数量。

接下来的 $m$ 行，每行三个整数 $a_i,b_i,w_i$，表示一条连接城市 $a_i,b_i$ 且长度为 $w_i$ 的道路。两个城市间最多只有一条道路。

保证所有城市是相互联通的。也就是说，任何一对城市，都有一条相互可达的路径，但不一定是直接相连。

保证所有数据的 $n, m$ 各自之和均不超过 $300000$。

输出格式

第一行输出一个整数 $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

提示

【样例解释】

城市和道路如图所示。如果 Baltazar 把他的魔法药水使用在第二条道路上（连接城市 $3$ 和 $5$ 的），那么城市 $1$ 和 $n$ 之间最短的距离将会增加 $1$。

【数据范围】

对于 $100\%$ 的数据，满足 $1\le t \le 10000,2\leq n \leq 3\times10^5,1\le m\le \min(3\times 10^5,\dfrac{n\times (n-1)}{2}), 1\le a_i,b_i\le n,a_i\neq b_i,1\le w_i\le 10^9$。

本题满分 $110$ 分。