题目描述

AtCoder 王国有 $N$ 个城市，分别称为城市 $1,2,\ldots,N$，以及 $M$ 条道路，分别称为道路 $1,2,\ldots,M$。
道路 $i$ 双向连接城市 $A_i$ 和 $B_i$，长度为 $C_i$。
可以通过一些道路在任意两个城市之间旅行。

由于财政困难，王国决定只维护 $N-1$ 条道路，以便人们仍然可以通过这些道路在任意两个城市之间旅行，并且放弃其余的道路。

设 $d_i$ 是在使用仅维护的道路从城市 $1$ 前往城市 $i$ 时必须使用的道路总长度。打印一种选择维护的道路的方式，使得 $d_2+d_3+\ldots+d_N$ 最小。

约束条件

• $2 \leq N \leq 2\times 10^5$
• $N-1 \leq M \leq 2\times 10^5$
• $1 \leq A_i < B_i \leq N$
• $(A_i,B_i)\neq(A_j,B_j)$，$i\neq j$。
• $1\leq C_i \leq 10^9$
• 可以通过一些道路在任意两个城市之间旅行。
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

输出

以任意顺序打印维护道路的索引，之间用空格分隔。
如果有多个解决方案，则可以打印其中任何一个。

示例输入 1

3 3
1 2 1
2 3 2
1 3 10

示例输出 1

1 2

以下是维护道路的可能选择和相应的 $d_i$ 值。

• 维护道路 $1$ 和 $2$：$d_2=1$，$d_3=3$。
• 维护道路 $1$ 和 $3$：$d_2=1$，$d_3=10$。
• 维护道路 $2$ 和 $3$：$d_2=12$，$d_3=10$。

因此，维护道路 $1$ 和 $2$ 可以最小化 $d_2+d_3$。

示例输入 2

4 6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1

示例输出 2

3 1 2