#include<stdio.h>
#include<algo.h>
FILE *f,*g;
long m1[400500],m2[400500],m3[400500],z,i,m,n,ind[400500],v1[200500],v2[200500],suma,nr,j,lv1,lv2,p1,p2,parinte[200000];
int cmp(long a,long b)
{ return m3[a]<m3[b]; }
int verif(long x,long y)
{ while(parinte[x]!=0) x=parinte[x]; while(parinte[y]!=0) y=parinte[y]; p1=x; p2=y;
  if(x!=y) return 1; else return 0;
}
void uneste(long x,long y)
{ while(x!=0) { z=parinte[x]; parinte[x]=p2; x=z; } }
int main()
{ f=fopen("apm.in","r"); g=fopen("apm.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++) fscanf(f,"%ld%ld%ld",&m1[i],&m2[i],&m3[i]);
  for(i=1;i<=m;i++) ind[i]=i;
  sort(ind+1,ind+m+1,cmp);
  nr=0; j=0; suma=0;
  while(nr<n-1)
   { j++; 
     if(verif(m1[ind[j]],m2[ind[j]])) { uneste(m1[ind[j]],m2[ind[j]]); nr++; suma+=m3[ind[j]]; v1[nr]=m1[ind[j]]; v2[nr]=m2[ind[j]]; }
   }
  fprintf(g,"%ld\n%ld\n",suma,nr);
  for(i=1;i<=nr;i++) fprintf(g,"%ld %ld\n",v1[i],v2[i]);
  fclose(g);
  return 0;
}