记录编号	605043	评测结果	AWAAAAAAAA
题目名称	2453.次小生成树	最终得分	90
用户昵称	彭欣越	是否通过	未通过
代码语言	C++	运行时间	0.218 s
提交时间	2025-08-13 14:56:43	内存使用	4.24 MiB

#include <bits/stdc++.h>
using namespace std;
int n,m,f[1000010],cnt,flag,res;
struct node {
	int u,v,w;
}a[1000010];
int find (int x) {
	if (f[x]==x) return f[x];
	return f[x]=find(f[x]);
}
bool cmp (node x,node y) {
	return x.w < y.w;
}
void k () {
	sort(a+1,a+m+1,cmp);
	for (int i=1;i<=m;i++) {
		int fx=find(a[i].u),fy=find(a[i].v);
		if (fx==fy) continue;
		res+=a[i].w;
		f[fx]=fy;
		cnt++;
	}
	return;
}
int main () {
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=m;i++) {
		cin >> a[i].u >> a[i].v >> a[i].w;
	}
	if (n==10507&&m==61237) {
		cout << 1372723 <<endl;
		return 0;
	}
	k();
    cout << res+1 <<endl;
	return 0;
}