题目描述

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

图用以下形式给出：

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

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 与 $y$ 之间有一条边，边权为 $z$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行有三个整数，代表一条边。

输出格式

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

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

4

数据规模

对于所有数据，保证 $2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,x≠y,1≤z≤10000$。