#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)
{return *(int *)a-*(int *)b;}
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);
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;
}