#include <fstream.h>
ifstream fin("apm.in");
ofstream fout("apm.out");

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

muchie e[400000],f[400000];
long c;
char v[400000];
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;
fin>>n>>m;

for (i=1;i<=m;i++)
fin>>e[i].x>>e[i].y>>e[i].cost;


quick(1,m);

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

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

j=2;

for (i=2;i<=n-1;i++)
{while (v[e[j].x]==v[e[j].y]) j++;
 v[e[j].x]=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;
}