#include<stdio.h>
#define dim 200005
#define Dim 400005
using namespace std;

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

Muchie G[Dim];
int n,m,i,comp[dim],min,max,j,sum,v[dim];
int nrm; //nrm=nr muchii selectate. ptr a obtine un ap de cost minim, trebuie sa fie egal cu nr noduri-1

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++) 
 comp[i]=i;
 
 sort(1,m);
 
 for(i=1; nrm<n-1 ;i++)
if(comp[G[i].n1] != comp[G[i].n2]) //varfurile muchiei fac parte din componente diferite
  {nrm++; v[nrm]=i; sum+=G[i].c;
    if(comp[G[i].n1] < comp[G[i].n2]) {min=comp[G[i].n1]; max=comp[G[i].n2];}
	else {min=comp[G[i].n2]; max=comp[G[i].n1];}
	
	for(j=1;j<=n;j++)
	 if(comp[j]==max) comp[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;
}