#5504. 【模板】最小生成树

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

题目描述

如题,给出一个无向图,求出最小生成树,输出最小边权和。

输入格式

第一行包含两个整数 N,M ,表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 X_i,Y_i,Z_i ,表示有一条长度为 Z_i 的无向边连接结点 X_i,Y_i

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。

样例

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

数据范围与提示

数据规模:

对于 100\% 的数据: 1\le N\le 2 \times 10^5 1\le M\le 5 \times 10^5