#include <cstdio>
#include <cstdlib>

int *tt,*rg;

struct muchie
{
	int x,y,cost;
};

int sort(const void *a,const void *b)
{
	muchie *aa=(muchie *)a,*bb=(muchie *)b;
	if(aa->cost>bb->cost)
		return 1;
	else
		return -1;
}

int find(int x)
{
	int tata,tmp;
	
	//gasesc varful arborului (si sper sa nu cad)
	for(tata=x;tt[tata]!=tata;tata=tt[tata]);
	
	//compresia drumurilor
	while(tt[x]!=x)
	{
		tmp=tt[x];
		tt[x]=tata;
		x=tmp;
	}
	
	//...
	return tata;
}

void join(int x,int y)
{
	int ttx=find(x),tty=find(y);
	
	//leg arborele mai mic de cel mai mare (cu sarma)
	if(rg[ttx]<rg[tty])
		tt[ttx]=tt[tty];
	else
		tt[tty]=tt[ttx];
	
	//daca rangurile lor erau egale, cresc rangul rezultatului (arborele definit de ttx) cu 1
	if(rg[ttx]==rg[tty])
		rg[ttx]++;
}

int main()
{
	int n,m,count,cost=0,i;
	FILE *f=fopen("apm.in","r"),*g=fopen("apm.out","w");
	fscanf(f,"%d %d\n",&n,&m);
	muchie *a=new muchie[m],*res[n-1];
	tt=new int[n+1],rg=new int[n+1];
	
	for(i=0;i<=n;i++)
	{
		tt[i]=i;
		rg[i]=0;
	}
	
	count=n-1;
	
	for(i=0;i<m;i++)
		fscanf(f,"%d %d %d\n",&a[i].x,&a[i].y,&a[i].cost);
	
	qsort(a,m,sizeof(muchie),sort);
	
	i=0;
	while(count)
	{
		if(find(a[i].x)!=find(a[i].y))
		{
			join(a[i].x,a[i].y);
			res[count-1]=&a[i];
			count--;
			cost+=a[i].cost;
		}
		
		i++;
	}
	
	fprintf(g,"%d\n%d\n",cost,n-1);
	for(i=0;i<n-1;i++)
		fprintf(g,"%d %d\n",res[i]->x,res[i]->y);
	
	return 0;
}