mst.cpp

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

const int MAX = 1e5 + 10;

pair <int, pair <int,int> > p[MAX];
int id[MAX], vertices, arestas, testes, ans;

int root(int x){
    while(id[x] != x){
        id[x] = id[id[x]];
        x = id[x];
    }
    return x;
}

void init(int n){
    for(int i = 1; i <= n; i++)
        id[i] = i;
}

void join(int a, int b){
    a = root(a);
    b = root(b);
    id[a] = b;
}

int main(){
    scanf("%d", &testes);
    while(testes--){
        scanf("%d %d", &vertices, &arestas);
        for(int i = 0; i < arestas; i++){
            int a,b,c;
            scanf("%d %d %d", &a, &b, &c);
            p[i] = make_pair(c, make_pair(a,b));
        }
        init(vertices);
        sort(p,p+arestas);
        ans = 0;
        for(int i = arestas-1; i > -1; i--){
            int x = p[i].second.first;
            int y = p[i].second.second;
            int cost = p[i].first;
            if(root(x) != root(y)){
                ans += cost;
                join(x,y);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}