kruskal
#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 2000000000
using namespace std;
const int M=200004;
const int N=5005;
int n,m,tot;
struct NODE{
int x,y,dis;
bool operator < (const NODE &a){
return this->dis < a.dis;
}
}bian[M];
int fa[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int find(int x){
if(fa[x]==x) return fa[x];
return find(fa[x]);
}
inline void kruskal(){
tot=0;
int ans=0;
for(int i=1;i<=m;i++){
if(fa[find(bian[i].x)]!=fa[find(bian[i].y)]){
fa[find(bian[i].x)]=fa[find(bian[i].y)];
tot++;
ans=ans+bian[i].dis;
}
if(tot==n-1){
printf("%d",ans);
break;
}
}
return ;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int x,y,z;
x=read();y=read();z=read();
bian[i].x=x;bian[i].y=y;bian[i].dis=z;
}
sort(bian+1,bian+m+1);
kruskal();
return 0;
}
prim
#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 2000000000
using namespace std;
const int M=200004;
const int N=5005;
int n,m,tot;
bool vis[N];
int dis[N];
struct NODE{
int to,nex,v;
}bian[M*2];
int head[M*2];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y,int z){
bian[++tot].nex=head[x];
bian[tot].to=y;
bian[tot].v=z;
head[x]=tot;
return;
}
inline void prim(){
int cnt=0,now=1;
int minn=inf;
int k,ans=0;
for(int i=1;i<=n;i++) dis[i]=inf;
dis[1]=0; vis[1]=1;
for(int i=head[1];i;i=bian[i].nex){
dis[bian[i].to]=min(dis[bian[i].to],bian[i].v);
}
while(cnt<n-1){
minn=inf;
vis[now]=1;
for(int i=1;i<=n;i++){
if(!vis[i]&&minn>dis[i]){
now=i;
minn=dis[i];
}
}
ans=ans+minn;
for(int i=head[now];i;i=bian[i].nex){
if(!vis[bian[i].to]){
int lgr=bian[i].to;
if(bian[i].v<dis[lgr]){
dis[lgr]=bian[i].v;
}
}
}
cnt++;
}
printf("%d",ans);
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int x,y,z;
x=read();y=read();z=read();
add(x,y,z);
add(y,x,z);
}
prim();
return 0;
}