#include <fstream.h>
#define NMAX 200001
#define MMAX 400001
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,L[NMAX],i,j,k=0,x,y,z;
long long ct=0;
struct muchie{int x,y,c;};
muchie u[MMAX],v[MMAX];

void sortare(int s, int d)
{int aux,i=s,j=d,pi=0,pj=1;
 muchie aux1;
 if(s<d)
  {while(i<j)
    {if(u[i].c>u[j].c) {aux1=u[i]; u[i]=u[j]; u[j]=aux1; aux=pi; pi=pj; pj=aux;}
     i+=pi; j-=pj;
    }
   sortare(s, i-1); sortare(i+1, d);
  }
}

int main()
{f>>n>>m;
 for(i=1;i<=m;i++) f>>u[i].x>>u[i].y>>u[i].c;
 sortare(1, m);
 for (i=1;i<=n;i++) L[i]=i;
 i=1;
 while(k<n-1)
  {x=u[i].x;
   while(L[x]!=x) x=L[x];
   y=u[i].y;
   while(L[y]!=y) y=L[y];
   if(x!=y)
    {k++; ct=ct+u[i].c;
     v[k]=u[i];
     z=u[i].y;
     while(L[z]!=z) z=L[z];
     L[z]=x;
    }
   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;
}