题目描述

AC 王国有 $n$ 座城市，编号为 $1\sim n$，然后有 $m$ 条双向道路。

现在国王 Gordon 为了降低道路养护成本，只打算留下其中的 $n-1$ 条路，并且保证这些路能连通全国。

首都是 $1$ 号城市，国王希望留下来的这些边能使得 $1$ 号城市到其他城市的距离总和最小。

现在 Gordon 把交通网地图交给了你，请你来解决这个问题。

输入格式

第一行为 $n,m(1\le n\le 2\times 10^5, n-1\le m\le 2\times 10^5)$。

往下每一行表示一条边，前两个数是无向边两端，第三个数是长度。

图保证连通，无重边无自环，且边长长度保证不大于 $10^9$。

输出格式

一行由空格隔开的数，输出留下来的边的编号，若是有多种方案，可以随便输出其中一种，且对于同一种方案中哪条边先输出也无要求。

3 3
1 2 1
2 3 2
1 3 10

1 2

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

3 1 2