http://oj.chilanggialai.edu.vn/problem/cloj01net

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+1;
const int Lim=1e6;

struct deptrai{
    int u,v,w,id;
} edge[N];
int n,m;

vector<int> sorty[Lim+1];
int lab[N];
int u,v,w;
int ans;

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for (int i=1;i <= m;i++) {
        cin >> u >> v >> w;
        edge[i] = {u, v, w, i};
        sorty[w].push_back(i);
    }
    for (int i=1;i <= n;i++)
        lab[i] = -1;
    int cntt=0;
    for (int i=1;i <= Lim;i++) {
        if (cntt == n) break;
        if (sorty[i].size() == 0) continue;
        for (auto id : sorty[i]) {
            if (cntt == n) break;
            u = (edge[id].u), v = (edge[id].v);
            while(lab[u] > 0) 
                u = lab[u];
            while(lab[v] > 0)
                v = lab[v];

            if (u != v) {
                cntt++;
                ans += edge[id].w;
                if (lab[u] > lab[v])
                swap(u, v);
                lab[u] += lab[v];
                lab[v] = u; 
            }
        }
    }
    cout << ans;
    return 0;
}