#include<fstream.h>
long p,i,j,min,poz,a,b,c,x1,y1,s[10000],t[10000],m,n,v[1000][1000],sum,k,x[10000],y[10000];
ifstream f("apm.in");
ofstream g("apm.out");
int main ()
{
f>>n>>m;
for (i=0;i<m;i++)
	{f>>a>>b>>c;
	v[a][b]=v[b][a]=c;}
for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		if (v[i][j]==0 && i!=j)
			v[i][j]=2000;
for (i=2;i<=n;i++) s[i]=1;
poz=1;
for (i=2;i<=n;i++)
	{min=2000;
	 for (k=1;k<=n;k++)
		if (s[k]==0)
		{for (j=1;j<=n;j++)
			if (s[j] && v[j][k]<min)
				{min=v[j][k];x1=j;y1=k;
				p=j;}}
	 x[i]=x1;y[i]=y1;
	 s[p]=0;
	 t[p]=poz;
	 sum+=min;
	 poz=p;
	 for (j=1;j<=n;j++)
		if (s[j]&&v[j][poz]<v[j][t[poz]])
			s[j]=poz;
	}
g<<sum<<'\n';
g<<n-1<<'\n';
for (i=2;i<=n;i++) g<<x[i]<<" "<<y[i]<<'\n';
return 0;
}