#include<fstream.h>

ofstream fout("apm.out");

int n,m,s[180],d[100],k,i,p,j,a[180][180],lin,col,min;

void citire()
{       int x,y,z;
	ifstream fin("apm.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		if(i==j) a[i][j]=0;
		else a[i][j]=a[j][i]=32000;
	for(i=1;i<=m;i++)
	{	fin>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
	}
	fin.close();
}

int main()
{	citire();
	s[1]=1;
	for(k=1;k<n;k++)
	{	min=32000;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(s[i]==1&&s[j]==0&&min>a[i][j])
				{	min=a[i][j];
					lin=i;
					col=j;
				}
		d[lin]=col;
		p+=min;
		s[col]=1;
	}
	fout<<p<<"\n";
	fout<<n-1<<"\n";
	for(i=1;i<=n;i++)
        	if(d[i]!=0) fout<<i<<" "<<d[i]<<"\n";
	fout.close();
	return 0;
}