#include<fstream.h>
#define dmax 400002

long vf1[dmax],vf2[dmax],c[dmax],a[dmax],ctotal,nrm,v[dmax];

long divide(long p, long q)
{
 long st=p, dr=q, x=c[p], y=vf1[p], z=vf2[p];
 
 while (st<dr)
	 {
	  while (st<dr && c[dr]>=x) 
		  dr--;
	  c[st]=c[dr];
	  vf1[st]=vf1[dr];
	  vf2[st]=vf2[dr];
	  while (st<dr && c[st]<=x)
		  st++;
	  c[dr]=c[st];
	  vf1[dr]=vf1[st];
	  vf2[dr]=vf2[st];
	 }
 c[st]=x;
 vf1[st]=y;
 vf2[st]=z;
 
 return st;
}

void qsort(long p, long q)
{
 long m=divide(p,q);
 
 if (m-1>p)
	 qsort(p,m-1);
 if (m+1<q)
	 qsort(m+1,q);	
}

int main()
{
 long n,m,i,j,min,max;
	
 ifstream fin("apm.in");
 fin>>n>>m;
 
 for (i=1; i<=m; i++)
	 {
      fin>>vf1[i]>>vf2[i]>>c[i];
	  v[i]=i;
	 }
 
 qsort(1,m);
 
 for (i=1; nrm<n-1; i++)
	 {
      if (v[vf1[i]] != v[vf2[i]])
		  {
		   nrm++;
		   a[nrm]=i;
		   ctotal=ctotal+c[i];
		   if (v[vf1[i]]<v[vf2[i]])
			   {
			    min=v[vf1[i]];
				max=v[vf2[i]];
				v[vf1[i]]=max;
			   } else
			   {
			    min=v[vf2[i]];
				max=v[vf1[i]];
				v[vf2[i]]=max;
			   }
		   for (j=1; j<=n; j++)
			   if (v[j]==min)
				   v[j]=max;
		  }
	 }
 
 ofstream fout("apm.out");
 fout<<ctotal<<'\n'<<nrm<<'\n';
 for (i=1; i<=nrm; i++)
	 fout<<vf1[a[i]]<<" "<<vf2[a[i]]<<'\n';
	
 fin.close();
 fout.close();
 
 return 0;
}