#include <fstream.h>
#define dim 200004
#define nrmax 400004
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {int x; int y; long cost;};
int n,m,A[dim],nr;
muchie e[nrmax];
int v[dim],min,max;
long cost;


int poz(int li, int ls)
{int i0=0,j0=-1,a;
muchie aux;

while (li<ls)
 {if (e[li].cost>e[ls].cost)
   {aux=e[li]; e[li]=e[ls]; e[ls]=aux;
    a=-j0; j0=-i0; i0=a;
   }
   li+=i0; ls+=j0;
 }
return li;
}
 

void sort(int li, int ls)
{int k;
 if (li<ls)
 {k=poz(li,ls);
  sort(li,k-1); sort(k+1,ls);
 }
}

int main()
{int i;
	fin>>n>>m;
for (i=1;i<=m;i++)
	fin>>e[i].x>>e[i].y>>e[i].cost;

sort(1,m);
for (i=1;i<=n;i++) v[i]=i;


for (i=1;nr<n-1;i++)
	if (v[e[i].x]!=v[e[i].y])
     {  nr++;
		A[nr]=i;
		cost+=e[i].cost;
		
		if (v[e[i].x]<v[e[i].y]) {min=v[e[i].x]; max=v[e[i].y];}
		 else
		  {min=v[e[i].y]; max=v[e[i].x];}
		  
		 for (int j=1;j<=n;j++) if (v[j]==max) v[j]=min;
	}
		 
	
fout<<cost<<'\n'<<n-1<<'\n';
for (i=1;i<=nr;i++)
	fout<<e[A[i]].x<<" "<<e[A[i]].y<<'\n';
fout.close();
return 0;
}