Boruvka 求调

#include <bits/stdc++.h>
using namespace std;

#define _rep(i,a,b) for (int i=(a);i<=(b);++i)

namespace IO {
};

using namespace IO;

const int N=5005;
const int M=200005;
const int inf=1e9;

int n,m;
int st[N];
int p[N];

struct edge {
    int a,b,c;
    bool flag;
} arr[M];

int find(int x) {
    return (p[x]==x)?p[x]:(p[x]=find(p[x]));
}

int boruvka() {
    int ans=0;
    _rep(i,1,n) p[i]=i;
    while (true) {
        bool flag=false;
        _rep(i,1,m) {
            if (arr[i].flag) continue;
            if (arr[i].c<arr[st[find(arr[i].a)]].c) st[find(arr[i].a)]=i;
            if (arr[i].c<arr[st[find(arr[i].b)]].c) st[find(arr[i].b)]=i;
        }
        _rep(i,1,n) {
            if (!st[i]) continue;
            if (find(arr[st[i]].a)==find(arr[st[i]].b)) continue;
            flag=true;
            arr[st[i]].flag=true,ans+=arr[st[i]].c;
            p[find(arr[st[i]].a)]=find(arr[st[i]].b);
        }
        _rep(i,1,n) st[i]=0;
        if (!flag) break;
    }
    return ans;
}

int main() {
    read(n),read(m);
    _rep(i,1,m) {
        int a,b,c;
        read(a),read(b),read(c);
        arr[i]={a,b,c};
    }
    arr[0].c=inf;
    writeln(boruvka());
    return 0;
}