#include <fstream.h>
#include <iostream.h>

#define nmax (400005)

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {long x,y; int cost;};

muchie e[nmax],f[nmax];
long c;
char v[nmax];
long n,m,nr;



long poz(long li, long ls)
{int i0=0,j0=-1,aux;
muchie a;

 while (li<ls)
 {if (e[li].cost>e[ls].cost)
  {a=e[li];
   e[li]=e[ls];
   e[ls]=a;
   aux=-j0;
   j0=-i0;
   i0=aux;
  }
  li+=i0;
  ls+=j0;
 }
return li;
}



void quick(long li, long ls)
{long k;
if (li<ls)
 {k=poz(li,ls);
  quick(li,k-1);
  quick(k+1,ls);
 }
}


int main()
{long i,x,y,j,nr;

fin>>n>>m;

for (i=1;i<=m;i++)
{fin>>x>>y>>j;
 if (x!=y)
 {nr++;
  e[nr].x=x;
  e[nr].y=y;
  e[nr].cost=j;
  }
}

m=nr;


quick(1,m);



v[e[1].x]=1;
v[e[1].y]=1;

f[1]=e[1];
c=e[1].cost;


nr=1;

for (i=2;i<n;i++)
{for (j=nr; v[e[j].x]==v[e[j].y]; j++);
 nr=j;
 v[e[j].x]=1;
 v[e[j].y]=1;
 c+=e[j].cost;
 f[i]=e[j];
}

fout<<c<<'\n'<<n-1<<'\n';

for (j=1;j<n;j++)
fout<<f[j].x<<" "<<f[j].y<<'\n';


fout.close();
return 0;
}