這題其實當時就應該想到，但只想到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;
}