Baltazar 决定去度假。目前，他身处 Baltazargrad，想要前往 Primošten。为了到达那里，他必须经过许多城市。共有 $n$ 个城市，它们由 $m$ 条双向道路连接。Baltazargrad 被标记为 1 号城市，Primošten 被标记为 $n$ 号城市。

Baltazar 不确定从 Baltazargrad 到 Primošten 的路线，因此他将使用 GPS。GPS 会引导他走最短路径到达目的地。

但 Baltazar 非常喜欢旅行，他可以在任意一条道路上（即使是他不会经过的道路）倾倒他的魔法药水，将其长度增加 2 公里。他只能在一条道路上倾倒药水。

不久他意识到，他必须在中午之前到达 Primošten 的 Zora 酒店办理入住，因此他不能让最短路径的长度增加太多。现在，他想知道他可以在多少条道路上倾倒魔法药水，使得从 Baltazargrad 到 Primošten 的最短距离恰好增加 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 \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$ 条道路的编号（输入中给出的顺序，从 1 开始）。

子任务

样例

输入 1

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

输出 1

2
2 4
0
3
2 4 6

说明 1

城市和道路如图所示。如果 Baltazar 在第 2 条道路（连接城市 1 和 3）或第 4 条道路（连接城市 3 和 5）上倾倒魔法药水，则城市 1 和 $n$ 之间的最短距离将增加 1。