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

void schimb(int &a, int &b)
{int aux=a; a=b= b=aux;
}

void divide(int s, int d, int &m)
{int i=s, j=d, pi=0, pj=1;
 while(i<j)
  {if(u[i].c>u[j].c) {schimb(u[i].c, u[j].c); schimb(pi, pj);
                     }
   i+=pi; j-=pj;                  
  } 
 m=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) {divide(s,d,m); sortare(s, m-1); sortare(m+1, d);}
}  

int main()  
{int i=1,j,k=0,x,y,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;  
}