最小生成树

题号：NC217433
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一个有 n 户人家的村庄，有 m 条路相互连接着。村里现在要修路，每条路都有一个成本价格，现在请你帮忙计算下，最少需要花费多少钱，就能让这 n 户人家连接起来。

$cost$ 为一个二维数组，每个元素是一个长度为 3 的一维数组 $a$ ， $a[0]$ 和 $a[1]$ 表示村庄 $a[0]$ 和村庄 $a[1]$ 有一条路，修这条路的成本价格为 $a[2]$ 。

每户之间可能有多条道路连接，但不可能自己与自己相连。

数据范围: $1 \le n \le 5 \times 10^3$ ， $1 \le m \le 5 \times 10^5$ ， $1 \le a[2] \le 10^4$

进阶：时间复杂度 $O(n+mlogm)$ ，空间复杂度 $O(n)$

示例1

复制

3,3,[[1,3,3],[1,2,1],[2,3,1]]

复制

示例2

复制

2,1,[[1,2,1]]

复制