最小生成树

题目描述

给定一张包含 $n$ 个点，$m$ 条边的无向带权图，请你求出这张图的最小生成树的边权之和。如果图上不存在生成树，则输出-1。

生成树指的是一个边的集合，这些边联通所有的点，且刚好构成一棵树。最小生成树指的是所有生成树中边权之和最小的生成树。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示点和边的数量。 接下来一行，每行包含三个整数$u,v,w$，表示 $u,v$ 之间存在一条边权为 $w$ 的边。

数据范围

$1 \le n, m \le 2 \times 10 ^ 5$ $1 \le u, v \le n$ $1 \le w \le 10^9$

样例 #1

样例输入 #1

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

样例输出 #1

6