Kruskal

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector <int> id;
vector <vector <int> > comp;

bool unionFind(int a, int b)
{
    int idA = id[a];
    int idB = id[b];

    if(idA == idB)
        return false;

    int tamA = comp[idA].size();
    int tamB = comp[idB].size();

    if(tamA > tamB)
        return unionFind(b, a);

    for(const auto nodo:comp[idA])
    {
        comp[idB].push_back(nodo);
        id[nodo] = idB;
    }

    comp[idA].clear();

    return true;
}

void prepararUnionFind(int cantNodos)
{
    ///Llamar a esta función antes de llamar
    ///a unionFind() !!!! IMPORTANTE!!!

    ///Cada nodo pertenece a su propio grupo
    comp.resize(cantNodos+1);
    id.resize(cantNodos+1);

    for(int i=0; i<cantNodos; i++)
    {
        comp[i].push_back(i);
        id[i] = i;
    }
}

struct arista
{
    int desde, hasta, costo;
};

bool operator<(const arista &a, const arista &b)
{
    return a.costo < b.costo;
}

int main()
{
    int n, m;
    int a, b, c;
    while(cin >> n >> m)
    {
        if(n == 0 && m == 0)
            break;
        vector <arista> aristas(m);
        prepararUnionFind(n);

        long long sumaTotal = 0;

        for(int i=0; i<m; i++)
        {
            cin >> a >> b >> c;
            aristas[i] = {a, b, c};
            sumaTotal += c;
        }

        sort(aristas.begin(), aristas.end());
        long long ahorro = 0;
        for(int i=0; i<m; i++)
        {
            if(unionFind(aristas[i].desde, aristas[i].hasta))
            {
                ahorro += aristas[i].costo;
            }
        }
        cout << sumaTotal - ahorro << endl;
    }

    /**
    Problemas de Arbol de Expansión Mínima:
    https://www.spoj.com/problems/ULM09/
    https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=975
    **/

    return 0;
}