#include<fstream>
#include<algorithm>
using namespace std;
struct Muchie{
  int e1, e2,c;
};
int tata[200009], grad[200009];
int n, m;
Muchie lista[400009];
int rez[200009], cmin;
int cmp(Muchie a, Muchie b){
  return a.c<b.c;
}
int tatal(int x){
  int v=x,v2=x,aux;
  while(tata[v]!=v)
    v=tata[v];
  while(tata[v2]!=v)
  {
    aux=tata[v2];
    tata[v2]=v;
    v2=aux;
  }
  return v;
}

bool bun (int x){
  int el1=lista[x].e1, el2=lista[x].e2;
  if(tatal(el1)==tatal(el2))
    return 0;
  return 1;
}
void reuneste(int x){
   int q,z, tq, tz;
   q=lista[x].e1;
   z=lista[x].e2;
   tq=tatal(q);
   tz=tatal(z);
   if(grad[tq]>grad[tz])
      tata[tz]=tq;
   else tata[tq]=tz;
   if(grad[tq]==grad[tz])
     grad[tz]++;
}
void APM(){
   int i, j;
   for(i=1;i<=n;i++)
   {
     tata[i]=i;
     grad[i]=1;
   }
   for(i=1,j=0;i<n;i++){
     while(!bun(j)) ++j;
     reuneste(j);
     rez[i]=j;
     cmin+=lista[j].c;
     ++j;
   }
}

int main(){
  int i;
  ifstream f("apm.in");
  f>>n>>m;
  for(i=0;i<m;i++){
    f>>lista[i].e1>>lista[i].e2>>lista[i].c;
  }
  f.close();
  sort(lista, lista+m, cmp);
  APM();
  ofstream g("apm.out");
  g<<cmin<<'\n';
  g<<n-1<<'\n';
  for(i=1;i<n;i++)
    g<<lista[rez[i]].e1<<' '<<lista[rez[i]].e2<<'\n';
  g.close();
  return 0;
}