题目描述

有编号从1到n的n个区域，这些区域之间通过路径进行连接。每条路径都连接两个区域，并且可以双向通行。

每个路径都有一个权值，这个权值由路径上的数字表示。每个路径上的数字都是唯一的。

现在，由于某种原因，所有的路径都处于阻塞状态。作为一名勇敢的探索者，塔子哥的任务是找出一种方式，疏通最少的路径，使得所有的区域都至少通过一个可以通行的路径与其他区域连接。

给定一部分路径的信息 [X,Y,M]，表示区域 X 和区域 Y 之间可以疏通一条路径，并且权值为 M。

塔子哥的目标是计算联通所有区域所需的路径的最小权值之和。如果无法联通所有区域，则输出-1。

输入格式

第一行为两个整数 $n,m$，分别表示区域和路径的数量。

接下来 $m$ 行每行三个整数 $x,y,v$，分别表示 $x$ 区域和 $y$ 区域之间有一条权值为 $v$ 的路径。

$1 \le x,y \le n \le 5000, 1 \le m \le 10^5, 1 \le v \le 1000$。

输出格式

计算联通所有区域的最小权值，如果无法联通，则输出 $-1$。

5 6
1 4 10
1 1 13
3 5 14
2 3 10
4 3 15
3 1 5

39