#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define nmax 200005
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

 int n,m,k;
 int dad[nmax],ind[nmax],nx[nmax],ny[nmax],nc[nmax];
 int sx[nmax],sy[nmax],v[nmax],res;

  bool cmp(int x,int y)
  { return nc[x]<nc[y]; }

  int Grupa(int x)
  { int i,num=0;

     while(dad[x]!=x)
     { num++; v[num]=x;
         x=dad[x];
     }

     for(i=1;i<=num;i++)
      dad[v[i]]=x;

   return x;
  }

int main()
{ int i,gr1,gr2;
    f>>n>>m;

    for(i=1;i<=m;i++)
     {f>>nx[i]>>ny[i]>>nc[i];
      ind[i]=i;
     }

    for(i=1;i<=n;i++)
     dad[i]=i;

    sort(ind+1,ind+m+1,cmp);

    for(i=1;i<=m;i++)
    { gr1=Grupa(nx[ind[i]]);
      gr2=Grupa(ny[ind[i]]);
      if (gr1!=gr2)
        {dad[gr2]=gr1; res+=nc[ind[i]];
         k++; sx[k]=nx[ind[i]]; sy[k]=ny[ind[i]];
        }
    }

    g<<res<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
     g<<sx[i]<<" "<<sy[i]<<"\n";

    return 0;
}