#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();
	for(i=2;i<=n;i++)
		s[i]=1;
	for(k=1;k<n;k++)
	{	min=32000;
		for(i=1;i<=n;i++)
		if(s[i]) if(min>a[s[i]][i]) { min=a[s[i]][i];
					      j=i;
					    }
		p+=a[j][s[j]];
		d[j]=s[j];
		for(i=1;i<=n;i++)
		if(s[i]&&a[i][s[i]]>a[i][j]) s[i]=j;
		s[j]=0;
	}
	fout<<p<<"\n"<<n-1<<"\n";
	for(i=1;i<=n;i++)
	     if(d[i]!=0) fout<<i<<" "<<d[i]<<"\n";
	fout.close();
	return 0;
}