UVa 11631 - Dark Roads

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define mx 200007

struct edge
{
    int a,b,c;

    edge(int _a, int _b, int _c)
    {
        a=_a, b=_b, c=_c;
    }

    bool operator < (const edge p) const
    {
        return (c < p.c);
    }
};


ll n,e;
vector <edge> graph;
ll leader[mx];

ll presm = 0;

int findr(int r)
{
    if(r==leader[r]) return r;
   
    int x = findr(leader[r]);
    leader[r] = x;

    return x;

    //else return leader[r] = findr(leader[r]);
}

ll mst()
{
    ll mstsm = 0;

    // init
    REP(i,mx) leader[i] = i;

    //find
    REP(i,SZ(graph))
    {
        int x = findr(graph[i].a);
        int y = findr(graph[i].b);

        if(x!=y) leader[y] = x , mstsm += graph[i].c;
    }
    return mstsm;
}

ll x,y,z;

int main()
{
   // freopen("F:/fout.txt", "w", stdout);
    while(scll(n,e) and n+e)
    {
        presm = 0;

        REP(i,e)
        {
            scll(x,y); scl(z);
            graph.push_back(edge(x,y,z));
            presm += z;
        }

        sort(ALL(graph));

        ll res = presm - mst();
        printf("%lld\n", res);

        graph.clear();
    }
    return 0;
}