#include<stdio.h>
#define dim1 200005
#define dim2 400005
using namespace std;

typedef struct Muchie {int n1, n2, c; };

Muchie G[dim2];

int NRM,n,m,i,cc[dim1],min,max,j,sum,v[dim1]; 

void sort(int prim, int ultim)
{int i,j;
Muchie x;

if(prim<ultim)
 {x=G[prim]; i=prim; j=ultim;
   while(i<j)
   {while(i<j && G[j].c>=x.c) j--;
     G[i]=G[j];
    while(i<j && G[i].c<=x.c) i++;
	  G[j]=G[i];
   }
   G[i]=x;
   
sort(prim, i-1);
sort(i+1,ultim);
 }
}


int main()
{
 FILE *f=fopen("apm.in","r"), *g=fopen("apm.out","w");
 
fscanf(f,"%d%d",&n,&m);
 for(i=1;i<=m;i++)
 fscanf(f,"%d%d%d", &G[i].n1, &G[i].n2, &G[i].c);
 
 for(i=1;i<=n;i++) 
	cc[i]=i;
 
 sort(1,m);
 
 for(i=1; NRM<n-1 ;i++)
if(cc[G[i].n1] != cc[G[i].n2]) 
  {NRM++; v[NRM]=i; sum+=G[i].c;
    
	if(cc[G[i].n1] < cc[G[i].n2]) 
		{min=cc[G[i].n1];
		max=cc[G[i].n2];}

	else {min=cc[G[i].n2]; max=cc[G[i].n1];}
	
	for(j=1;j<=n;j++)
	 if(cc[j]==max) cc[j]=min;
	
  }
 
fprintf(g,"%d\n",sum);
fprintf(g,"%d\n",NRM);

 for(i=1;i<=NRM;i++)
  fprintf(g,"%d %d\n",G[v[i]].n1,G[v[i]].n2);
 
fclose(f);
fclose(g);
return 0;
}