道路削减

题目描述

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$ 最小。

输入格式

输入按以下格式从标准输入给出：

N M
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_M B_M C_M

输出格式

以任意顺序输出被维护的道路的编号，用空格隔开。

如果存在多个解，可以输出任意一个。

样例

3 3
1 2 1
2 3 2
1 3 10

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$ 最小。

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

3 1 2

数据范围

• $2 \le N \le 2 \times 10^5$
• $N-1 \le M \le 2 \times 10^5$
• $1 \le A_i \lt B_i \le N$
• 当 $i \neq j$ 时，$(A_i, B_i) \neq (A_j, B_j)$。
• $1 \le C_i \le 10^9$
• 利用一些道路可以在任意两个城市之间往返。
• 输入中的所有值均为整数。

提示

答案不唯一，输出任意合法解即可。