102524: [AtCoder]ABC252 E - Road Reduction

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

The Kingdom of AtCoder has $N$ cities called City $1,2,\ldots,N$ and $M$ roads called Road $1,2,\ldots,M$.
Road $i$ connects Cities $A_i$ and $B_i$ bidirectionally and has a length of $C_i$.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only $N-1$ roads so that one can still travel between any two cities using those roads and abandon the rest.

Let $d_i$ be the total length of the roads one must use when going from City $1$ to City $i$ using only maintained roads. Print a choice of roads to maintain that minimizes $d_2+d_3+\ldots+d_N$.

Constraints

  • $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$
  • One can travel between any two cities using some roads.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the indices of roads to maintain, in arbitrary order, with spaces in between.
If multiple solutions exist, you may print any of them.


Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of $d_i$.

  • Maintain Road $1$ and $2$: $d_2=1$, $d_3=3$.
  • Maintain Road $1$ and $3$: $d_2=1$, $d_3=10$.
  • Maintain Road $2$ and $3$: $d_2=12$, $d_3=10$.

Thus, maintaining Road $1$ and $2$ minimizes $d_2+d_3$.


Sample Input 2

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

Sample Output 2

3 1 2

Input

题意翻译

给定 $ n $ 个点 $ m $ 条边的无向连通简单图,每条边为 $ a_i $ 到 $ b_i $,权值为 $ c_i $。你需要构造一棵生成树,最小化点 $ 1 $ 在生成树上到其它所有点的距离和,输出生成树的所有边的序号。如果有多个方案随便输出一个即可。

Output

分数:500分

问题描述

阿特科德王国拥有$N$个城市,分别称为City $1,2,\ldots,N$,以及$M$条道路,分别称为Road $1,2,\ldots,M$。

第$i$条道路双向连接City $A_i$和$B_i$,长度为$C_i$。

可以使用一些道路在任何两个城市之间旅行。

由于财政困难,该国决定只维护$N-1$条道路,以便仍然可以使用这些道路在任何两个城市之间旅行,并放弃其余道路。

设$d_i$是从City $1$到City $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)$如果$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

加入题单

上一题 下一题 算法标签: