#include <iostream.h>
#include <fstream.h>

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

ifstream fin(IN);
ofstream fout(OUT);

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;

 fin>>n>>m;   
 for(i=1;i<=m;i++)
 {
  fin>>x[i]>>y[i]>>c[i];                
  ind[i]=i;
 }
 fin.close();

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

 quick(1,m);

 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];
  }
 }

 fout<<ans<<endl;
 fout<<n-1<<endl;
 for(i=1;i<=n-1;i++)
  fout<<x[vans[i]]<<" "<<y[vans[i]]<<endl;
 fout.close();
  
 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(c[i]>c[j])
  {
   aux=ind[i];
   ind[i]=ind[j];
   ind[j]=aux;

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