题目描述

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

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

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

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

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

输入描述

第一行为两个整数 $n,m(1\le n\le 5000,1 \le m \le 10^5)$，分别表示区域和路径的数量。

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

输出描述

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

样例

输入

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

输出

39