hdu 1879

#include<stdio.h>
#include<stdlib.h>
#define N 100
struct node {
int x,y,dis;
}road[N*N];
int pre[N];
int find(int n) {
return pre[n]=n==pre[n]?n:find(pre[n]);
}
int cmp(const void *a,const void *b) {
return (*(struct node *)a).dis>(*(struct node *)b).dis?1:-1;
}
int main() {
int n,m,i,j,k,a,b,c,len,sum,f1,f2,cnt;
while(scanf("%d",&n),n ) {
for(i=1;i<=n;i++)
pre[i]=i;
m=n*(n-1)/2;
len=0;cnt=0;
for(i=1;i<=m;i++) {
scanf("%d%d%d%d",&a,&b,&c,&k);
if(k) {
f1=find(a);
f2=find(b);
if(f1!=f2) {
cnt++;
pre[f2]=f1;
}
}
road[len].dis=c;
road[len].x=a;
road[len++].y=b;
}
sum=0;
qsort(road,len,sizeof(road[0]),cmp);
for(i=0;cnt<n&&i<len;i++) {
f1=find(road[i].x);
f2=find(road[i].y);
if(f1!=f2) {
cnt++;
sum+=road[i].dis;
pre[f2]=f1;
}
}
printf("%d ",sum);
}
return 0;
}