Unnamed

#include <stdio.h>

void bsort(int a[], int b[][2], int n);
void swap(int *x, int *y);

int main(void)	{
	/*
	LANG: C
	TASK: cyclades
	*/
	int N, M, DIA[50000][2], APO[500000], OLA[1000000];
	int NISIA[1000], MONAD[1000]={0}, MON[1000]={0};
	int v, i, k, bots, r, y;
	FILE *fp;
	y=0;
	r=1;
	fp=fopen("cyclades.in", "r");
	fscanf(fp, "%d %d", &N, &M);
	for(i=0; i<M; i++)	{
		fscanf(fp, "%d %d %d\n", &DIA[i][0], &DIA[i][1], &APO[i]);
	}
	fclose(fp);
	fp=fopen("cyclades.out", "w");
	if(M<N-1)	{
		fprintf(fp, "%d\n", -1);
		goto end;
	}
	bsort(APO, DIA, M);
	for(i=0; i<M; i++)	{
		OLA[i]=DIA[i][0]; 
		OLA[M+i]=DIA[i][1];
	}
	for(i=0; i<2*M; i++)	{
		for(v=0; v<N; v++)	{
			if(OLA[i]==(v+1))	{
				MONAD[v]++;
				break;
			}
		}
	}
	for(i=0; i<N; i++)	{
		if(MONAD[i]==0)	{
			fprintf(fp, "%d\n", -1);
			goto end;
		}
	}
	for(i=0; i<M; i++)	{
		if(MONAD[DIA[i][0]-1]==1 && MONAD[DIA[i][1]-1]==1 && N>2)	{
			fprintf(fp, "%d\n", -1);
			goto end;
		}
	}
	for(i=1; i<=N; i++)	{
		NISIA[i-1]=i;
	}
	bots=APO[0];
	NISIA[DIA[0][0]-1]=NISIA[DIA[0][1]-1]=0;
	MON[DIA[0][0]-1]=MON[DIA[0][1]-1]=1;
	for(i=1; i<M; i++)	{
		if(NISIA[DIA[i][0]-1]!=0 || NISIA[DIA[i][1]-1]!=0)	{
			bots+=APO[i];
			NISIA[DIA[i][0]-1]=0;
			NISIA[DIA[i][1]-1]=0;
			MON[DIA[i][0]-1]++;
			MON[DIA[i][1]-1]++;
			r++;
		}
	}
	while(r<N-1)	{
		for(i=0; i<M; i++)	{
			if(MON[DIA[i][0]-1]==1 && MON[DIA[i][1]-1]==1)	{
				for(k=i+1; k<M; k++)	{
					if((DIA[i][0]==DIA[k][0] || DIA[i][0]==DIA[k][1] || DIA[i][1]==DIA[k][0] || DIA[i][1]==DIA[k][1]))	{
					 	bots+=APO[k];
					 	MON[DIA[k][0]-1]++;
					 	MON[DIA[k][1]-1]++;
				 		r++;
						y=1;
					 }
					 if(y==1)	{
					 	goto nexty;
					 }
				}
			}
		}
		nexty:
		y=0;
	}
	fprintf(fp, "%d\n", bots*4);
	end:
	fclose(fp);
	return(0);
	
}

void bsort(int a[], int b[][2], int n)	{
	int i, flag=0;
	while(flag==0)	{
		flag=1;
		for(i=0; i<=n-1; i++)	{
			if(a[i]<a[i-1])	{
				swap(&a[i], &a[i-1]);
				swap(&b[i][0], &b[i-1][0]);
				swap(&b[i][1], &b[i-1][1]);
				flag=0;
			}
		}
	}
	return;
}

void swap(int *x, int *y)	{
	int t;
	t=*x;
	*x=*y;
	*y=t;
	return;
}