#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{ int x,y,cost;}v[400001];
int i,m,n,costmin,j,nr,ma,nrm,mi,x,y,mu[400001],t[400001],c[200001];
int poz(int li, int ls)
{ int i,j;
  muchie x;
  x=v[li];
  i=li;
  j=ls;
  while(i<j)
  {while(i<j&&v[j].cost>=x.cost)
    --j;
    v[i]=v[j];
    while(i<j&&v[i].cost<=x.cost)
        ++i;
    v[j]=v[i];

  }
  v[i]=x;
  return i;
}
void quick(int li,int ls)
{
    int k;
    if(li<ls)
    {k=poz(li,ls);
     quick(li,k-1);
     quick(k+1,ls);
    }
}


int main()
{ f>>n>>m;
  for(i=1;i<=m;++i)
     f>>v[i].x>>v[i].y>>v[i].cost;
quick(1,m);

    for(i=1;i<=n;++i)
        c[i]=i;
    nr=0;
    i=1;
    nrm=0;
    costmin=0;
    while(nr<n-1)
    {x=v[i].x;
    y=v[i].y;
     if(c[x]!=c[y])
     {if(c[x]>c[y])
        {ma=c[x];
         mi=c[y];
         }
         else
         {ma=c[y];
          mi=c[x];

         }
         for(j=1;j<=n;++j)
             if(c[j]==ma)
               c[j]=mi;
         costmin=costmin+v[i].cost;
         ++nr;

         mu[nrm+1]=y;
        mu[nrm+2]=x;
        nrm=nrm+2;
     }
        ++i;
    }
   g<<costmin<<'\n';
    g<<nr<<'\n';
  for(i=1;i<=nrm;i=i+2)
      g<<mu[i]<<' '<<mu[i+1]<<'\n';
    return 0;
}