#include <stdio.h>

#define Nmax 128

int a[4][Nmax],n,m,c,t[Nmax],nr,rang[Nmax];

int mult(int x)
{
	if(x!=t[x])
		t[x]=mult(t[x]);
	return t[x];
}

void combina(int x,int y)
{
	x=mult(x);
	y=mult(y);
	if(rang[x]>rang[y]) t[y]=x; else
	if(rang[y]>rang[x]) t[x]=y; else
	{
		t[x]=y;
		++rang[y];
	}
}


void swap(int i,int j)
{
		int tmp;
		tmp=a[2][i];
		a[2][i]=a[2][j];
		a[2][j]=tmp;
		tmp=a[1][i];
		a[1][i]=a[1][j];
		a[1][j]=tmp;
		tmp=a[0][i];
		a[0][i]=a[0][j];
		a[0][j]=tmp;
}


void qsort(int st,int dr)
{
	int i=st,j=dr,x=a[2][(i+j)/2];
	do
	{
			while(a[2][i]<x) ++i;
			while(a[2][j]>x) --j;
			if(i<=j)
				{
					swap(i,j);
					++i;
					--j;
				}
	}while(i<=j);

	if(st<j)	qsort(st,j);
	if(i<dr)	qsort(i,dr);
}


int main()
{
	int i;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
		scanf("%d%d%d",&a[0][i],&a[1][i],&a[2][i]);
	qsort(1,m);
	for(i=1;i<=n;++i)
		{
			t[i]=i;
		}
	for(i=1;i<=m;++i)
		{
			if(mult(a[0][i])!=mult(a[1][i]))
				{
					combina(a[0][i],a[1][i]);
					c+=a[2][i];
					a[3][i]=1;
					++nr;
				}
		}
	printf("%d\n",c);
	printf("%d\n",nr);
	for(i=1;i<=m;++i)
		{
			if(a[3][i]==1)
				printf("%d %d\n",a[0][i],a[1][i]);
		}
	return 0;
}