当前没有测试数据。

E - 路径简化

得分：$500$ 分

问题描述

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

由于经济困难，王国决定只维护 $N-1$ 条道路，以便通过这些道路仍然可以在任意两个城市之间旅行，且其他道路被废弃。

令 $d_i$ 表示用仅维护的道路从 City $1$ 到 City $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$
• 如果 $i\neq j$，有 $(A_i,B_i)\neq(A_j,B_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$

输出

打印维护道路的索引，以任意顺序，之间用空格隔开。
如果存在多个解，则可以打印其中之一。

3 3
1 2 1
2 3 2
1 3 10

1 2

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

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

因此，维护 Road $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