Kruskal

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU{
    vector<int> parent;
    DSU(int n){
        parent = vector<int>(n, -1);
    }
    int get(int x){
        if(parent[x]<0){
            return x;
        }else{
            return parent[x] = get(parent[x]);
        }
    }
    bool same_set(int a, int b){
        return get(a) == get(b);
    };
    bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(same_set(x, y)) return false;
        if(parent[x]>parent[y]){
            swap(x, y);
        }
        parent[x]+=parent[y];
        parent[y] = x;
        return true;
    }
};

struct Path{
    int a, b;
    ll weight;
    bool operator<(const Path &v) const{
        return weight<v.weight;
    }
};

int n, m;
vector<Path> paths;
ll mst;

int main(){
    //freopen("kruskal.in", "r", stdin);

    cin >> n >> m;
    paths.resize(m);
    for(int i=0; i<m; i++){
        cin >> paths[i].a >> paths[i].b >> paths[i].weight;
    }
    sort(paths.begin(), paths.end());
    DSU dsu(n+1);
    for(int i=0; i<m; i++){
        if(!dsu.same_set(paths[i].a, paths[i].b)){
            dsu.unite(paths[i].a, paths[i].b);
            mst+=paths[i].weight;
        }
    }
    cout << mst << '\n';

    return 0;
}