A24634.道路削减

时间限制：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}$

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

样例 $1$：
以下是可能选择维护的道路以及 $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$。