Prim
# include<iostream>
# include<cstring>
using namespace std;#define INF 0x3f3f3f3f const int N=1001,M=100010;
int n,m;
int g[N][N];
int dist[N];
bool st[N]={0};int prim(){memset(dist,0x3f,sizeof dist);int res=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++)if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;if(i&&dist[t]==INF)return INF;if(i) res+=dist[t];st[t]=1;for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);}return res;
}
int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int s,t,w;scanf("%d%d%d",&s,&t,&w);g[s][t]=w;g[t][s]=w;}cout<<prim();return 0;
}c
Kruskal
# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;#define INF 0x3f3f3f3f const int N=1001,M=5001;
int n,m;
int p[N];
int cnt=0;
struct Edge{int a,b,w;bool operator< (const Edge &W)const{return w<W.w;}
}edges[M];
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}int kruskal(){sort(edges,edges+m);for(int i=1;i<=n;i++)p[i]=i;int res=0,cnt=0;for(int i=0;i<m;i++){int a=edges[i].a,b=edges[i].b,w=edges[i].w;a=find(a),b=find(b);if(a!=b){p[a]=b;res+=w;cnt++;}}if(cnt<n-1)return INF;return res;
}
int main(){cin>>n>>m;for(int i=0;i<m;i++){scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].w);}cout<<kruskal();return 0;
}
