题目描述

强哥所在的社区有 $N$ 个居民区，编号为 $1, 2, \ldots, N$，以及 $M$ 条双向道路，编号为 $1, 2, \ldots, M$。 第 $i$ 条道路连接居民区 $A_i$ 和 $B_i$，长度为 $C_i$。 任意两个居民区之间都可以通过若干条道路互相到达。

由于社区预算有限，只能维护 $N-1$ 条道路，其余道路将暂时关闭。要求维护后的道路仍然保证任意两个居民区之间可以互相到达。

对于每个居民区 $i$（$2 \leq i \leq N$），定义 $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$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

输出一行，包含 $N-1$ 个整数，表示被维护的道路编号，编号之间用空格分隔（顺序不限）。

输入输出样例

样例 1

输入

3 3
1 2 1
2 3 2
1 3 10

输出

1 2

说明 维护道路 1 和 2 时，$d_2 = 1$，$d_3 = 3$，总和最小。

样例 2

输入

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

输出

3 1 2

数据范围

• $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$
• 任意两个居民区之间都可以通过若干条道路互相到达
• 输入中的所有数值均为整数