最小生成树

【题目描述】

给定一个带权无向图，包含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边为 $(a_i, b_i)$，权值为 $c_i$。这个图不一定是简单图。

请找出最小生成树。

【输入】

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $c_i$，表示一条连接顶点 $a_i$ 和 b_i、权值为 $c_i 的边。

$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$ $e_2$ ... $e_{N - 2}$

$X$ 是最小生成树中边的权值之和。$e_i$ 是最小生成树中边的编号。 如果有多个正确输出，输出其中任意一个。

【输入样例】

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

【输入样例2】

4 3
0 1 1
1 2 2
3 1 3

【输出样例2】

6
0 1 2

【输入样例3】

6 5
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000

【输出样例3】

5000000000
0 1 2 3 4

【数据范围】

• $1 \leq N \leq 500000$
• $N - 1 \leq M \leq 500000$
• $0 \leq a_i, b_i < N$
• $0 \leq c_i \leq 1000000000$
• 给定的图是连通的。

【来源】

Library Checker（yosupo06） minimum_spanning_tree

本题为 special judge（输出任意合法解），暂不可本地评测。