本题目可以用 最小生成树之 Kruskal 算法 解

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
int fa[N], n, m;
long long ret; // 不开 long long 见祖宗
struct node {
	int x, y, z;
}e[M];

bool cmp(node n1, node n2) {
	return n1.z < n2.z;
}
void INIT() { // 初始化每个节点的父节点都是自己
	for (int i = 1; i <= n; i++) {
		fa[i] = i; // 相当于一个图有 n 个节点，也有 n 个联通块
	} // 可以说是一个图没有边，初始化，Kruskal 的基本思想就是贪心
} 
int dfs(int x) { // 并查集，不懂看后面
	return fa[x] == x ? x : fa[x] = dfs(fa[x]);
    // fa[x] = dfs(fa[x]) 是一个路径压缩
}
void kruskal() {
	int cnt = 0;
	sort(e+1, e+m+1, cmp); // 排序所有的边
	for (int i = 1; i <= m; i++) { // 枚举所有的边
		int fx = dfs(e[i].x); // find
		int fy = dfs(e[i].y);
		if (fx != fy) { // 可以通过并查集函数来理解
			fa[fx] = fy; //
			ret += e[i].z;
			cnt++; // 这个没有用，但是这个可以计数是否可以构成最小生成树
		}
	}
	cout << ret;
}

int main() {
    cin >> n >> m;
	INIT();
    for (int i = 1; i <= m; i++) {
    	scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
	}
	kruskal();
    return 0;
}

并查集