TOI11: Sacred Places

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

#define lli long long
#define tiii tuple<int, int, int>

priority_queue<tiii> q; /// (w, u, v)
vector<int> DS;
vector<int> ranks;
int nv, ne;

int DSFind(int x){
    if(DS[x] == x){
        return x;
    } else {
        return DS[x] = DSFind(DS[x]);
    }
}

void DSUnion(int x, int y){
    int fx = DSFind(x);
    int fy = DSFind(y);
    if(ranks[fx] > ranks[fy]){
        DS[fy] = fx;
    } else {
        DS[fx] = fy;
        if(ranks[fx] == ranks[fy]){
            ++ranks[fy];
        }
    }
    return;
}

lli KruskalMaxST(){
    lli cnt = 0;
    while(!q.empty()){
        int w = get<0>(q.top());
        int u = get<1>(q.top());
        int v = get<2>(q.top());
        q.pop();
        if(DSFind(u) != DSFind(v)){
            DSUnion(u, v);
            cnt += w - 1;
        }
    }
    return cnt;
}

int main(){

    int u, v, w;

    scanf("%d %d", &nv, &ne);
    DS.assign(nv + 1, 0);
    ranks.assign(nv + 1, 1);
    for(int i = 1; i <= nv; ++i){
        DS[i] = i;
    }

    for(int i = 0; i < ne; ++i){
        scanf("%d %d %d", &u, &v, &w);
        q.emplace(w, u, v);
    }

    cout << KruskalMaxST();

    return 0;
}