3840 - 最小生成树prim

给你一副无向图G,求最小生成树的边权总和,不存在输出-1

输入

第一行输入两个整数$n,m$  , 分别表示点数与边数
接下来$m$行每行输入三个整数$a,b,c$ ,表示a,b之间有一条权值为c的边


 

输出

输出一个整数

样例

输入

3 3
1 2 1
1 3 1
2 3 2

输出

2

提示

$1 \le n \le 1000, 1 \le m \le 10000$ 
$1 \le a,b,c \le 1000$ 
 

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题