11264: [yosupo] Graph - Minimum Spanning Tree
[Creator : ]
Description
Given a weighted undirected graph with $N$ vertices and $M$ edges. The $i$-th edge is $(a_i, b_i)$ and has a weight of $c_i$. This graph may not be simple.
Find the minimum spanning tree.
Find the minimum spanning tree.
Input
$N$ $M$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
:
$a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
:
$a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$
Output
$X$
$e_0$ $e_1$ $e_2$ ... $e_{N - 2}$
$X$ is the sum of the weights of the edges in the minimum spanning tree. $e_i$ is the index of the edge in the minimum spanning tree.
If there are multiple correct output, print any of them.
$e_0$ $e_1$ $e_2$ ... $e_{N - 2}$
$X$ is the sum of the weights of the edges in the minimum spanning tree. $e_i$ is the index of the edge in the minimum spanning tree.
If there are multiple correct output, print any of them.
Constraints
- $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$
- The given graph is connected.
- $N - 1 \leq M \leq 5\times 10^5$
- $0 \leq a_i, b_i < N$
- $0 \leq c_i \leq 10^9$
- The given graph is connected.
Sample 1 Input
4 7
0 1 4
0 2 2
0 3 3
1 2 6
1 3 8
2 3 1
1 1 0
Sample 1 Output
7
1 5 0
Sample 2 Input
4 3
0 1 1
1 2 2
3 1 3
Sample 2 Output
6
0 1 2
Sample 3 Input
6 5
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
Sample 3 Output
5000000000
0 1 2 3 4