A3091 | 道路削减

时间限制：2000ms

内存限制：256MB

现有 $N$ 座城市 $1, 2, \ldots, N$ 和 $M$ 条道路 $1, 2, \ldots, M$。
城市 $A_i$ 和 $B_i$ 由一条长度为 $C_i$ 的双向道路 $i$ 连接。
可以通过某些道路在任意两座城市之间通行。

现希望只保留 $N-1$ 条道路，并且使用保留的道路仍然可以来往于任意两个城市之间。

令 $d_i$ 是仅使用保留的道路时，从城市 $1$ 到城市 $i$ 的最短路径。
请你输出一种道路的选择方案，使 $d_2+d_3+\ldots+d_N$ 最小。

$\large{数据范围}$

- $2 \leq N \leq 2\times 10^5$
- $N-1 \leq M \leq 2\times 10^5$
- $1 \leq A_i \lt B_i \leq N$
- $(A_i,B_i)\neq(A_j,B_j)$ 若 $i\neq j$.
- $1\leq C_i \leq 10^9$
- 可以通过某些道路在任意两座城市之间通行。
- 所有输入数值均为整数。

对于每个测试文件输入格式如下：

$\tt{N\ M}$

$\tt{A_1\ B_1\ C_1}$
$\tt{A_2\ B_2\ C_2}$
$\tt{\vdots}$
$\tt{A_M\ B_M\ C_M}$

按任意顺序输出要保留的道路编号，中间用空格隔开。
如果存在多个解决方案，输出任意一个即可。