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

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: xiongyingjie

题目描述

给定结点数为 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