#include<stdio.h>
long n,m,c[200000],a[400000];
long long costul;

struct muchie
	{
	long e1,e2;
	int cost;
	} g[400000],aux;

void read ()
	{
	FILE *f=fopen("apm.in","r");
	fscanf(f,"%ld%ld",&n,&m);
	long i;
	for (i=1;i<=m;++i)
		fscanf(f,"%ld%ld%d",&g[i].e1,&g[i].e2,&g[i].cost);
	fclose(f);
	}

void quick (int s, int d)
	{
	int m=(s+d)/2,i=s,j=d,x;
	x=g[m].cost;
	while (i<=j)
		{
		while (g[i].cost<x)
			i++;
		while (x<g[j].cost)
			--j;
		if (i<=j)
			{
			aux=g[i];
			g[i]=g[j];
			g[j]=aux;
			i++;
			j--;
			}
		}
	if (s<j)
		quick(s,j);
	if (i<d)
		quick(i,d);
	}

void init ()
	{
	long i;
	for (i=1;i<=n;++i)
		c[i]=i;
	}

void solve ()
	{
	long i,j,nr=0,min,max;
	for (i=1; nr<n-1; ++i)
		if (c[g[i].e1]!=c[g[i].e2])
			{
			a[++nr]=i;
			costul+=g[i].cost;
			if (c[g[i].e1]<c[g[i].e2])
				{
				min=c[g[i].e1];
				max=c[g[i].e2];
				}
			else
				{
				min=c[g[i].e2];
				max=c[g[i].e1];
				}
			for (j=1;j<=n;++j)
				if (c[j]==max)
					c[j]=min;
			}
	}

void write ()
	{
	FILE *f=fopen("apm.out","w");
	fprintf(f,"%lld\n%ld\n",costul,n-1);
	long i;
	for (i=1;i<=n-1;++i)
		fprintf(f,"%ld %ld\n",g[a[i]].e1,g[a[i]].e2);
	fclose(f);
	}

int main ()
{
read ();
quick (1,m);
init ();
solve ();
write ();
return 0;
}