← 返回题目列表

AtCoder · abc252_e

H. 道路减少

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

AtCoder王国有 N 城市称为 City 1,2,\ldots,N 和 M 道路称为路 1,2,\ldots,M.
路 i 连接城市 A_i 和 B_i 双向且长度为 C_i.
人们可以使用某些道路在任意两个城市之间旅行。

在财政困难下,王国决定仅维持 N-1 道路,以便人们仍然可以使用这些道路在任意两个城市之间行驶并放弃其余道路。

让 d_i 是从城市出发时必须使用的道路总长度 1 前往城市 i 仅使用维护良好的道路。打印要维护的道路选择,以最大限度地减少 d_2+d_3+\ldots+d_N.

约束

  • 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
  • (A_i,B_i)\neq(A_j,B_j) if i\neq j.
  • 1\leq C_i \leq 10^9
  • 人们可以使用某些道路在任意两个城市之间旅行。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

输出

以任意顺序打印要维护的道路索引,其间有空格。
如果存在多个解决方案,您可以打印其中任何一个。


示例输入 1

3 3
1 2 1
2 3 2
1 3 10

示例输出 1

1 2

以下是维护道路的可能选择以及相应的值 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.


示例输入 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