#include <iostream>
#include <fstream>

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

struct M{
int a, b, c;
}x[400001], y[400001];
int T[200001];

void QS(int st, int dr)
{if(st<dr)
 {int i=st, j=dr, d=0;
  swap(x[(st+dr)/2], x[st]);

  while(i<j)
  {if(x[i].c>x[j].c)swap(x[i], x[j]), d=1-d;
   i+=d;
   j-=1-d;
  }
  QS(st, i-1);
  QS(i+1, dr);
 }
}

int R(int a)
{if(a==T[a])return a;
 else return T[a]=R(T[a]);
}

void L(int a, int b)
{if(T[a]<T[b])T[b]=T[a];
 else T[a]=T[b];
}

int main()
{   int n, m, sol=0, k=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    fin>>x[i].a>>x[i].b>>x[i].c;
    QS(1, m);

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

    for(int i=1;i<=m && k<n-1;i++)
    {int a1=R(x[i].a), b1=R(x[i].b);

     if(a1!=b1)
     {y[++k]=x[i];
      sol+=x[i].c;

      L(a1, b1);
     }
    }

    fout<<sol<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
    fout<<y[i].a<<" "<<y[i].b<<"\n";

    return 0;
}