MST

#include <bits/stdc++.h>
using namespace std;
/************************/
#define MAX_N 100000
#define MAX_M 200000
typedef struct{
    int f[MAX_N];
    void init(int N){
        for(int i=0;i<N;i++)
            f[i] = i;
    }
    int find(int v){
        if(f[v] == v) return v;
        return f[v] = find(f[v]);
    }
    bool same(int a, int b){
        return find(a) == find(b);
    }
    void Union(int a, int b){
        f[find(a)] = find(b);
    }
}disjoinset;
typedef struct{
    int d1,d2,w; // d = destination, w = weight
}edge;
edge E[MAX_M];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        int p,q,c; // p & q = two vert of a edge, c = weight of edge
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&p,&q,&c);
            E[i] = (edge){p,q,c};
        }
        sort(E,E+m,[](edge a, edge b){return a.w < b.w;}); // sort Edges
        //Kruskal
        disjoinset ds;
        ds.init(n);
        int sum=0,count=0;
        for(int i=0;i<m;i++){
            if(!ds.same(E[i].d1,E[i].d2)){
                count++;
                sum += E[i].w;
                ds.Union(E[i].d1,E[i].d2);
            }
            if(count == n-1) break;
        }
        //Ouput
        if(count == n-1)
            printf("%d\n",sum);
        else
            printf("-1\n");
    }
    return 0;
}