estrada_noic.cpp

#include <bits/stdc++.h>
#define MAX 200010
using namespace std;
struct aresta
{
	int a,b;
	int dis;
};
int pai[MAX];
aresta grafo[MAX];
int _find(int a)
{
	if(pai[a] == a)
		return a;
	return pai[a] = _find(pai[a]);
}

void _union(int a, int b)
{
	pai[a] = b;
}
bool comp(aresta a, aresta b)
{
	return a.dis < b.dis;
}
int Kruskal(int m)
{
	int soma = 0;
	for(int i = 0; i < m; i++)
	{
		int a = _find(grafo[i].a);
		int b = _find(grafo[i].b);
		if(a != b)
		{
			soma+=grafo[i].dis;
			_union(a,b);
		}
	}
	return soma;
}
int main()
{
	int n, m;
	while(scanf("%d%d", &n, &m) && (n+m))
	{
		for(int i = 0; i < n; i++)
			pai[i] = i;
		int total = 0;
		for(int i = 0; i < m; i++)
			scanf("%d%d%lld", &grafo[i].a, &grafo[i].b, &grafo[i].dis), total+=grafo[i].dis;
		sort(grafo, grafo+m, comp);
		printf("%d\n", total - Kruskal(m));
	}
	return 0;
}