AT_abc252_e [ABC252E] Road Reduction

题目描述

AtCoder 王国有 $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$

输出格式

请输出被保留的道路的编号，编号之间用空格分隔，顺序不限。
如果有多种方案，输出任意一种均可。

输入输出样例 #1

输入 #1

3 3
1 2 1
2 3 2
1 3 10

输出 #1

1 2

输入输出样例 #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

说明/提示

限制条件

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

样例说明 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$ 最小。

由 ChatGPT 4.1 翻译