UOJ Logo LFYZ Online Judge

LFYZOJ

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

统计

问题描述

给你一张 $n$ 个点 $m$ 条边的图,求出它的最小生成树。

输入格式

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

下来 $m$ 行每行三个正整数 $u,v,w$,代表 $u$ 和 $v$ 之间有一条长度为 $w$ 的无向边。

输出格式

一个整数,是最小生成树的边的长度和。

样例一

input

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

output

7

数据范围与约定

对于 $100\%$ 的数据,$n \leq 5000$,$m \leq 200000$,$w \leq 10000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$