#include<stdio.h>

#define IN "apm.in"
#define OUT "apm.out"
#define maxn 400100

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

long gr[maxn],x[maxn],y[maxn],c[maxn];
long n,m,ans,ind[maxn];
long vans[maxn];

long grupa(long);
void reuniune(long,long);
void quick(long,long);
long poz(long,long);

int main()
{
 long i;
    
 fscanf(fin,"%ld %ld\n",&n,&m);
 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%ld %ld %ld\n",&x[i],&y[i],&c[i]);
  ind[i]=i;
  gr[i]=c[i];
 }
 fclose(fin);

 quick(1,m);

 for(i=1;i<=n;i++)
  gr[i]=i;

 for(i=1;i<=m;i++)
 {
  if(grupa(x[ind[i]])!=grupa(y[ind[i]]))
  {
   ans=ans+c[ind[i]];
   reuniune(x[ind[i]],y[ind[i]]);
   vans[0]++;
   vans[vans[0]]=ind[i];
  }
 }

 fprintf(fout,"%ld\n",ans);
 fprintf(fout,"%ld\n",n-1);
 for(i=1;i<=n-1;i++)
  fprintf(fout,"%ld %ld\n",x[vans[i]],y[vans[i]]);
 fclose(fout);

 return 0;
}

long grupa(long i)
{
 if(gr[i]==i)
  return i;

 gr[i]=grupa(gr[i]);
 return gr[i];
}

void reuniune(long i,long j)
{
 gr[grupa(i)]=grupa(j);
}

void quick(long st,long dr)
{
 if(st<dr)
 {
  long k=poz(st,dr);
  quick(st,k-1);
  quick(k+1,dr);
 }
}

long poz(long st,long dr)
{
 long i=st;
 long j=dr;
 long ii=0;
 long jj=-1;
 long aux;

 while(i<j)
 {
  if(gr[i]>gr[j])
  {
   aux=ind[i];
   ind[i]=ind[j];
   ind[j]=aux;

   aux=gr[i];
   gr[i]=gr[j];
   gr[j]=aux;

   aux=ii;
   ii=-jj;
   jj=-aux;
  }
  i=i+ii;
  j=j+jj;
 }
 return i;
}