最小生成树权值

题目描述

给定一张包含 n 个顶点、m 条边的无向带权图。请计算连接全部顶点所需的最小边权总和。

若原图不连通，无法得到包含全部顶点的生成树，则输出 -1。

图中可能存在重边，边权也可能为负数。

输入格式

第一行两个整数 n、m。

接下来 m 行，每行三个整数 u、v、w，表示顶点 u 和 v 之间有一条权值为 w 的无向边。

输出格式

输出最小生成树的边权和；若图不连通，输出 -1。

5 7
1 2 2
1 3 5
2 3 1
2 4 4
3 4 2
3 5 6
4 5 3

8

数据范围

• 1 <= n <= 100000
• 0 <= m <= 200000
• -1000000000 <= w <= 1000000000
• 答案可能超过 32 位整数范围