#include<fstream.h>
#include<iostream.h>
int a[1000][1000],
   s[1000],t[1000];
long i,j,k,x,y,n,m,min;
ifstream f("apm.in");
ofstream h("apm.out");
void citire()
	 {int y,z;
	  f>>n>>m;
	 for(i=1;i<=m;i++)
	{f>>x>>y>>z;
	 a[x][y]=z;
	 a[y][x]=z;
	}
	for(i=1;i<=n;i++)
	 for(j=1;j<=n;j++)
	   if(i!=j && a[i][j]==0)  a[i][j]=32000;
	x=1;
	}
int main()
{citire();
int cost=0;
for(i=1;i<=n;i++)
    s[i]=x;
s[x]=0;

for(i=2;i<=n;i++)
	   {min=32000;
		    {  for(j=1;j<=n;j++)
			   if(s[j]!=0 && min>a[s[j]][j])   {min=a[s[j]][j];k=j;}
		       if(min!=32000)
			  {t[k]=s[k];s[k]=0;cost+=a[k][t[k]];
			   for(j=1;j<=n;j++)
			     if(s[j]!=0 )
			       if(a[s[j]][j]>a[k][j]) s[j]=k;
			 }
		     }
	   }

h<<cost<<'\n';
h<<n-1<<'\n';
for(i=2;i<=n;i++)
    {h<<t[i]<<" "<<i;
    h<<'\n';}
return 0;
}