#include <iostream>
#include <fstream>
using namespace std;
const int NMAX=400005;
ifstream be("apm.in");
ofstream ki("apm.out");
struct el{
int x,y,ertek;
}a[NMAX];
int l[200005];
int n,m;
int kivalaszt[200005];
int osszertek;
void read()
{
    be>>n>>m;
    for(int i=1;i<=m;i++)
        be>>a[i].x>>a[i].y>>a[i].ertek;
    for(int i=1;i<=n;i++)
        l[i]=i;
}
void rendez()
{
    el seged;
    bool c=true;
    do{
            c=true;
        for(int i=1;i<m;i++){

            if(a[i].ertek>a[i+1].ertek)
        {
            seged=a[i];
            a[i]=a[i+1];
            a[i+1]=seged;
            c=false;
        }
        }
    }while(!c);

}
bool slove()
{
    int i=0,j=1;
    int id;
    while((i<n-1)&&(j<=m))
    {
        if(l[a[j].x]!=l[a[j].y])
        {
         i++;
         kivalaszt[i]=j;
         osszertek=osszertek+a[j].ertek;
         id=l[a[j].y];
         for(int k=1;k<=n;k++)
            if(id==l[k])
            l[k]=l[a[j].x];
        }
        j++;
    }
    return i==n-1;
}
int main()
{
    read();
    rendez();

  if(slove())
  {
      ki<<osszertek<<"\n";
      ki<<n-1<<"\n";
      for(int i=1;i<n;i++){
        ki<<a[kivalaszt[i]].y<<" "<<a[kivalaszt[i]].x<<" ";
        ki<<"\n";
      }
  }
    return 0;
}