这题其实当时就应该想到，但只想到kruskal的程度，觉得不对，就没敢敲。看了下解题报告，原来可以巧妙的利用一下n号集合，怎么说呢，把边从大到小排序，然后像做最大生成树那样增加边。
1.如果两个顶点在同一集合，就把这个集合同一挂到n号集合下面去，由于题目中没有n这个点，所以挂在n下的就算找到圈了。
2.如果两个顶点不在同一集合,且两个顶点都不在n集合，那么请随意:-)。
3.如果有一个顶点在n集合中，这里要特别注意，害我RE了无数回，要把不是n的那个集合挂到n下面去。想想嘛，本来找到圈了，结果挂到0-n-1下面，又会认定为没有圈了。
（此题算法参考了标程，但是标程写得实在太挫了，好像故意要让人看不懂似的，跟tc里的变态们一个样，难道标程就不应该写的友好一点？bsz）
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
int a;
int b;
int v;
bool operator<(node other)
{return v<other.v;}
}e[2000010];
int ans;
int f[100100];
int r[100000];
int n,m;
int find(int x)
{
if(f[x]==x)
return x;
else f[x]=find(f[x]);
return f[x];
}
int main()
{
//freopen("Pseudoforest.in","r",stdin);
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
if(n==0&&m==0) break;
for(i=0;i<=n;i++)
f[i]=i;
for(i=0;i<m;i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
sort(e,e+m);
for(i=m-1;i>=0;i--)
{
int a=find(e[i].a);
int b=find(e[i].b);
if(a>b)
swap(a,b);
if(a!=b)
{
ans+=e[i].v;
f[a]=b;
}
else if(a==b&&b!=n)
{
ans+=e[i].v;
f[a]=n;
}
}
printf("%d\n",ans);
}
return 0;
}