J12 例题-1 【模版】最小生成树

题目描述

给定结点数为 $n$ ，边数为 $m$ 的带权无向连通图 $G$ ，所有结点编号为 $1,2...... n$ 。

求 $G$ 的最小生成树的边权和。

输入格式

第一行两个正整数 $n,m$ 。

之后的 $m$ 行，每行三个正整数 $u_i,v_i,w_i$($1 \leq u_i,v_i \leq n$) ，描述一条连接结点 $u_i$ 和 $v_i$，边权为 $w_i$的边。

输出格式

一个整数表示 $G$ 的最小生成树的边权和。

样例输入

7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1

样例输出

16

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 5 \times 10^5$ ,$0 \leq w_i \leq 10^9$。