现有 N 座城市 1,2,…,N 和 M 条道路 1,2,…,M。
城市 A
i
和 B
i
由一条长度为 C
i
的双向道路 i 连接。
可以通过某些道路在任意两座城市之间通行。
现希望只保留 N−1 条道路,并且使用保留的道路仍然可以来往于任意两个城市之间。
令 d
i
是仅使用保留的道路时,从城市 1 到城市 i 的最短路径。
请你输出一种道路的选择方案,使 d
2
+d
3
+…+d
N
最小。
数据范围
2≤N≤2×10
5
N−1≤M≤2×10
5
1≤A
i
<B
i
≤N
(A
i
,B
i
)
=(A
j
,B
j
) 若 i
=j.
1≤C
i
≤10
9
可以通过某些道路在任意两座城市之间通行。
所有输入数值均为整数。
输入格式
对于每个测试文件输入格式如下:
N M
A
1
B
1
C
1
A
2
B
2
C
2
⋮
A
M
B
M
C
M
输出格式
按任意顺序输出要保留的道路编号,中间用空格隔开。
如果存在多个解决方案,输出任意一个即可。
样例组
输入#1
复制
3 3
1 2 1
2 3 2
1 3 10
输出#1
复制
1 2
输入#2
复制
4 6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
输出#2
复制
3 1 2
提示说明
样例 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