#include <fstream.h>
ifstream fin("apm.in");
ofstream fout ("apm.out");
int i,j,p,q,a[100][100],k=0,v[1000],min,c,x,y,l,s[100],cost;
long n,m;
int main ()
{
	fin>>n;
	fin>>m;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		a[x][y]=a[y][x]=c;
	}
	min=100000;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (a[i][j]<min && a[i][j]!=0)
			{
				min=a[i][j];
				p=i;
				q=j;
			}
		s[p]=s[q]=1;
		v[++k]=p;
		v[++k]=q;
		cost+=min;
	for (l=1;l<n-1;l++)
	{
		min=10000;
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				if (a[i][j]<min && s[i]+s[j]==1 && a[i][j]!=0)
				{
					min=a[i][j];
					p=i;
					q=j;
				}
				s[p]=s[q]=1;
				v[++k]=p;
				v[++k]=q;
				cost+=min;
	}
fout<<cost<<"\n";
fout<<k/2<<"\n";
for (i=1;i<=k;i++)
	{fout<<v[i]<<" "<<v[i+1]<<"\n";
i++;}
}