#GR0301. 最小生成树1

最小生成树1

题目描述

给你一张简单无向连通图,边权都为非负整数。你需要求出它的最小生成树,只需要输出边的权值和即可。

图用以下形式给出:

第一行输入两个整数 n,mn,m,表示图的顶点数、边数,顶点编号从 1 到 nn

接下来 mm 行,每行三个整数 x,y,zx,y,z,表示 xxyy 之间有一条边,边权为 zz

输入格式

第一行两个整数 n,mn,m

接下来 mm 行,每行有三个整数,代表一条边。

输出格式

输出一个数,表示最小生成树的权值和。

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

数据规模

对于所有数据,保证 2n1000,n1m100000,1x,yn,xy,1z100002≤n≤1000,n−1≤m≤100000,1≤x,y≤n,x≠y,1≤z≤10000