#include<stdio.h>
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
long s[200001],nm,min,cost,x,y,i,j,k,n,m,c,v[200001],a[2000][40000];
int main(){
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%ld%ld%ld",&x,&y,&c);
		a[x][y]=a[y][x]=c;}
	min=1001;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]<min){
				x=i;
				y=j;
				min=a[i][j];}
	s[x]=s[y]=1;
	v[1]=x;
	v[2]=y;
	k=2;
	cost=min;
	nm++;
	while(nm!=n-1){
		min=1001;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if((s[i]==0&&s[j]==1)||(s[i]==1&&s[j]==0))
					if(a[i][j]<min){
						x=i;
						y=j;
						min=a[i][j];}
		nm++;
		cost=cost+min;
		s[x]=s[y]=1;
		k++;
		v[k]=x;
		k++;
		v[k]=y;}
	fprintf(g,"%ld\n%ld\n",cost,nm);
	for(i=1;i<=k;i=i+2)
		fprintf(g,"%ld %ld\n",v[i],v[i+1]);
	fclose(f);
	fclose(g);
	return 0;}