mst.cpp

#include<bits/stdc++.h>

using namespace std ;

#define M 500000
#define pf printf
#define sf scanf
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 0 ; i< n ;i++ )

int arr[M] ;
int nodes ;

struct street{
int u , v , w ;

}var[M];
vector<street> roads;

bool comp(street a , street b ){
    return a.w < b.w ;

}

int find(int i){
    if(arr[i] ==  i ) return i ;
    else{
        arr[i]  = find(arr[i] );
        return arr[i] ;
    }
}

void make(int a , int b ){
    int u = find(a );
    int v = find(b );
    if(u != v ) arr[u] =  v ;

}

int mst(void){
int i , j, k, sum;
rep(i, nodes) arr[i] =  i ;

    sum =  roads[0].w ;
    make(roads[0].u , roads[0].v);

    for(i = 1 ; i < roads.size() ;i++)
    {
    if(find(arr[roads[i].u]  ) != find(arr[roads[i].v]) )
        {
            sum +=  roads[i].w ;
            make(roads[i].u ,  roads[i].v);
        }


    }

return sum ;
}

int main(){
    freopen("in.txt" , "r" , stdin );

int i , j , n  ,k;
while(scanf("%d%d",&n ,&k )){
    if(n+ k == 0) break ;

        nodes = n ;
        roads.clear() ;
        int sum = 0;
        for(i =0 ;i < k; i++){
            int u , v ,w ;
            scanf("%d%d%d",&u,&v ,&w );
            var[i].u =  u ;
            var[i].v =  v ;
            var[i].w =  w ;
            sum +=  w ;
        roads.push_back(var[i]);
        }

    sort(roads.begin() ,roads.end(), comp);

 k = mst();
pf("%d\n",sum-k);
}
return 0;}