#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct muchie
{
    int x,y,c;
}v[400000],s[400000];
int T[100000];

int compara(muchie p, muchie q)
{
    return p.c<q.c;
}

int tata(int x)
{
    if(T[x]==x)
        return x;
    return T[x]=tata(T[x]);
}

int main()
{
   int n,m,sum=0,k=0;
   int i,j;
   in>>n>>m;
   for(i=1;i<=m;i++)
    in>>v[i].x>>v[i].y>>v[i].c;
   for(i=1;i<=n;i++)
    T[i]=i;
   sort(v+1,v+m+1,compara);

   for(i=1;i<=m;i++)
   {
       if(tata(v[i].x)!=tata(v[i].y))
       {
           T[tata(v[i].y)]=tata(v[i].x);
           s[++k]=v[i];
           sum+=v[i].c;
       }
   }
   out<<sum<<endl<<k<<endl;
   for(i=1;i<=k;i++)
    out<<s[i].x<<" "<<s[i].y<<endl;


    return 0;
}