1428: Minimum Spanning Tree

题目

题目描述

给定一张 $n$ 个点，$m$ 条边的有权无向连通图，求最小生成树的边权和。

Input

请从 stdin 读入。

输入第一行为两个正整数 $n, m(1 \leq n \leq 5000, 1 \leq m \leq 2\times 10 ^ 5)$。

接下来 $m$ 行，第 $i$ 行为用空格隔开的整数 $u_i, v_i, w_i (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10000)$，表示第 $i$ 条边为从 $u_i$ 到 $v_i$。

输入可能存在重边与自环。

Output

请输出到 stdout 中。

输出一行，包含一个整数，表示你的答案。

Sample Input

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

3 3 1 2 3 2 3 1 3 1 2

Sample Output

6

3

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！