时间限制：2000ms 内存限制：256MB

现有 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 ​

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

n m
a1 b1 c1
a2 b2 c2
.........
am bm cm
输出格式

按任意顺序输出要保留的道路编号，中间用空格隔开。 如果存在多个解决方案，输出任意一个即可。 . 时间限制：2000ms 内存限制：256MB

现有 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 ​ 。