#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct el
{ int c,ind; } v[400005];

bool comp (el x,el y)
{ return x.c<y.c; }

 int n,m,dad[400005],dx[400005],dy[400005],nsol,sol,sx[400005],sy[400005],st[400005],k;

 int Mult(int x)
 { int i;
   k=1; st[k]=x;
   while(dad[x]!=x)
   { x=dad[x];
     k++; st[k]=x;
   }

   for(i=1;i<=k;i++)
    dad[st[i]]=x;
   return x;
 }

int main()
{ int i,nod1,nod2,m1,m2;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>dx[i]>>dy[i]>>v[i].c;

      v[i].ind=i;
    }
    sort(v+1,v+m+1,comp);

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

    for(i=1;i<=m;i++)
    {  nod1=dx[v[i].ind]; nod2=dy[v[i].ind];
        m1=Mult(nod1); m2=Mult(nod2);

      if (m1!=m2)
        {dad[m2]=m1;
         nsol++; sol+=v[i].c;
         sx[nsol]=nod1; sy[nsol]=nod2;
        }
    }

    g<<sol<<"\n"<<nsol<<"\n";

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

    return 0;
}