#include<iostream.h>
#include<fstream.h>
fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);
int n,m,l[100];
struct muchie{
	int x,y,c;
}u[20];
void init()
{  int i;
	for(i=1;i<=n;i++)
		l[i]=i;
}
 void citire()
 {   f>>n>>m;
	 int i=0,x,y,c;
	while(f>>x>>y>>c){
		i++;
		u[i].x=x;
		u[i].y=y;
		u[i].c=c;
	               }
	  f.close();m=i;
 }
 void sortare(){
	 int i,j;
	 muchie aux;
 for(i=1;i<m;i++)
	  for(j=i+1;j<=m;j++)
		if(u[i].c>u[j].c) { aux=u[i];
	                       u[i]=u[j];
							u[j]=aux;
		                   }
		
 }
 int main()
 {
	 int i=1,j,k=0,x,y,ct=0;
	 citire();
	 sortare();
	 init();
	 while(k<n-1)
	 {
		 if(l[u[i].x]!=l[u[i].y]) 
		 { k++; ct=ct+u[i].c;
		   x=l[u[i].x];
		   y=l[u[i].y];
		   for(j=1;j<=n;j++)
			    if(l[j]==x) l[j]=y;
		 }
		 i++;
     }
 g<<ct<<'\n'<<n-1<<'\n';
 for(i=1;i<=n-1;i++)  
   g<<u[i].y<<" "<<u[i].x<<"\n";
 g.close();
 return 0;

 }