最小生成树（Minimum Spanning Tree）

问题描述

给定一个含 $N$ 个顶点、$M$ 条边的连通无向加权图，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，权重为 $c_i$。
请找出一棵最小生成树（MST），即包含所有顶点、恰好 $N-1$ 条边、总权重最小的树。

输出该 MST 的总权重 $X$，以及所选边的索引序列 $e_0, e_1, \dots, e_{N-2}$（0-based）。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $N-1 \leq M \leq 5 \times 10^5$
• $0 \leq a_i, b_i < N$
• $0 \leq c_i \leq 10^9$
• 图是连通的

输入格式

$N\ M$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
:
$a_{M-1}\ b_{M-1}\ c_{M-1}$

输出格式

$X$
$e_0\ e_1\ \cdots\ e_{N-2}$

其中：

• $X$ 是 MST 的总权重；
• $e_i$ 是 MST 中第 $i$ 条边的原始输入索引（0-based）；
• 若存在多棵 MST，输出任意一种即可。

4 7
0 1 4
0 2 2
0 3 3
1 2 6
1 3 8
2 3 1
1 1 0

7
1 5 0

4 3
0 1 1
1 2 2
3 1 3

6
0 1 2

6 5
0 1 100000000
1 2 100000000
2 3 100000000
3 4 100000000
4 5 100000000

500000000
0 1 2 3 4