#include <fstream.h>     
#define NMAX 200001     
#define MMAX 400001     
ifstream f("apm.in");     
ofstream g("apm.out");     
int n,m,L[NMAX];     
struct muchie{int x,y,c;};     
muchie u[MMAX],v[MMAX];     
  
int divide(int s, int d)   
{int aux, i=s, j=d, pi=0, pj=1;   
 while(i<j)   
  {if(u[i].c>u[j].c) {aux=u[i].c; u[i].c=u[j].c; u[j].c=aux; aux=pi; pi=pj; pj=aux;}   
   i+=pi; j-=pj;                     
  }    
 return i;
}   
  
void init()    
{for (int i=1;i<=n;i++) L[i]=i;   
}     
  
void citire()     
{int i,x,y,c; f>>n>>m;     
  for(i=1;i<=m;i++) {f>>x>>y>>c; u[i].x=x; u[i].y=y; u[i].c=c;}     
  f.close();     
}     
  
void sortare(int s, int d)     
{int m;   
 if(s<d) {m=divide(s,d); sortare(s, m-1); sortare(m+1, d);}   
}     
  
int main()     
{int i=1,j,k=0,x,y;
 long long ct=0;     
 citire();     
 sortare(1, m);     
 init();     
 while(k<n-1)     
  {if (L[u[i].x]!=L[u[i].y])     
    {k++; ct=ct+u[i].c;     
     v[k]=u[i];     
     x=L[u[i].y];     
     y=L[u[i].x];   
     for (j=1;j<=n;j++) if(L[j]==x) L[j]=y;     
    }    
   i++;     
  }     
 g<<ct<<'\n'<<n-1<<'\n';     
 for(i=1; i<n; i++)     
  g<<v[i].x<<' '<<v[i].y<<'\n';     
 g.close(); f.close();     
 return 0;     
}