#include<fstream.h>
#include<stdlib.h>
int md[200001],X[400001],Y[400001],C[400001],N,M,c,p[400001],l[200001],n;
int mult(int x)
{if(md[x]==x) return x;
 md[x]=mult(md[x]);
 return md[x];}
void reun(int x,int y)
{md[mult(x)] = mult(y);}
int fs(const void *a, const void *b)
{if(C[(int)a]<C[(int)b]) return -1;
 if(C[(int)a]>C[(int)b]) return  1;
 return 0;}
void sort()
{int i,j,x;
 for(i=1;i<M;++i)
  for(j=i+1;j<=M;++j)
   if(C[p[i]]>C[p[j]])
   {x=p[i];p[i]=p[j];p[j]=x;}}
int main()
{ifstream f("apm.in");
ofstream g("apm.out");
f>>N>>M;
int i=1;
for(;i<=M;++i)
{f>>X[i]>>Y[i]>>C[i];
 md[i]=p[i]=i;}
//qsort((void *)(p+1),M,sizeof(p[0]),fs);
sort();
for(i=1;i<=M;++i)
 if(mult(X[p[i]])!=mult(Y[p[i]]))
 {c+=C[p[i]];
  reun(X[p[i]],Y[p[i]]);
  l[++n]=p[i];}
g<<c<<'\n'<<N-1<<'\n';
for(i=1;i<N;++i)
 g<<X[l[i]]<<' '<<Y[l[i]]<<'\n';
return 0;
}