#include<stdio.h>
#define nmax 200010
long h[nmax], vz[nmax], n, m, nh;
struct elem
{	long vf, c;
	elem *urm;
}	*a[nmax], *q;
struct muchie
{       long x, y;
}	t[nmax];
FILE *f, *g;

void read()
{	long i, x, y, c;
	fscanf(f, "%ld%ld", &n, &m);
	for(i=1; i<=m; i++)
	{	fscanf(f, "%ld%ld%ld", &x, &y, &c);
		q=new elem;
		q->vf=x; q->c=c; q->urm=a[y];
		a[y]=q;
		q=new elem;
		q->vf=y; q->c=c; q->urm=a[x];
		a[x]=q;
	}
}

void ins(long x, long y, long c)
{	long k, z;
	muchie tmp;
	nh++; k=nh;
	h[nh]=c; t[nh].x=x; t[nh].y=y;
	while(h[k/2]>h[k] && k>1)
	{	z=h[k/2]; h[k/2]=h[k]; h[k]=z;
		tmp=t[k/2]; t[k/2]=t[k]; t[k]=tmp;
		k=k/2;
	}
}

void del(long k)
{       long z, m;
	muchie tmp;
	z=h[nh]; h[nh]=h[k]; h[k]=z;
	tmp=t[nh]; t[nh]=t[k]; t[k]=tmp;
	nh--;
	while( ((h[k]>h[2*k] && 2*k<=nh) ||
	       (h[k]>h[2*k+1] && 2*k+1<=nh)) && k<nh)
	{     	if(2*k==nh)			m=2*k;
		else	if(h[2*k]<h[2*k+1])     m=2*k;
			else			m=2*k+1;
		z=h[m]; h[m]=h[k]; h[k]=z;
		tmp=t[m]; t[m]=t[k]; t[k]=tmp;
		k=m;
	}
}


int main()
{       long i, x, o=0, nr=0;
	muchie sol[nmax];
	f=fopen("apm.in", "r");
	g=fopen("apm.out", "w");
	read();
	sol[0].x=0; sol[0].y=0;
	x=1; vz[x]=1;
	do
	{	for(q=a[x]; q; q=q->urm)
			if(!vz[q->vf])
				ins(x, q->vf, q->c);
		while(vz[t[1].y] && nh)
			del(1);
		if(nh)
		{	o++;
			sol[o].x=t[1].x; sol[o].y=t[1].y;
			nr+=h[1];
			vz[t[1].y]=1;
			x=t[1].y;
			del(1);
		}
	}
	while(nh);
	fprintf(g, "%ld\n%ld\n", nr, o);
	for(i=1; i<=o; i++)
		fprintf(g, "%ld %ld\n", sol[i].x, sol[i].y);
	return 0;
}