#include<fstream.h>
#include<stdlib.h>
int md[200001],X[400001],Y[400001],C[400001],N,M,c,p[400001],l[200001],n=-1;
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 C[*(int *)a]-C[*(int *)b];}
int main()
{ifstream f("apm.in");
ofstream g("apm.out");
f>>N>>M;
int i;
for(;i<M;++i)
{f>>X[i]>>Y[i]>>C[i];
 md[i]=p[i]=i;}
qsort((void *)p,M,sizeof(p[0]),fs);
for(i=0;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=0;i<N-1;++i)
 g<<X[l[i]]<<' '<<Y[l[i]]<<'\n';
return 0;
}