MST裸题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=1010,M=100010;
struct Edge{
int a,b,w;
bool operator <(const Edge &W){
return w<W.w;
}
}e[M];
int n,m;
int p[N];
int find(int x){ // 并查集
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++){
int a=read(),b=read(),c=read();
e[i]={a,b,c};
}
sort(e,e+m);
ll ans=0;
for(int i=0;i<m;i++){
int a=e[i].a,b=e[i].b,c=e[i].w;
int fa=find(a),fb=find(b);
if(fa!=fb){
p[fa]=fb;
ans+=c;
}
}
cout<<ans;
return 0;
}