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

using namespace std;
struct muchie
{
    int x;
    int y;
    int c; //costul muchiei
}L[400003];
int T[200003], H[200003], n, m, nr_muchii;
int sol [400003][2];
int cost;
ofstream g("apm.out");
ifstream f("apm.in");

bool ord(muchie x,muchie y)
 {return (x.c<y.c);}

void citire()
{
    int k,i;

    f>>n>>m;
    for(i=1;i<=m;i++)
      f>>L[i].x>>L[i].y>>L[i].c;

    f.close();
}


int Rad(int nod)  //determina radacina arborelui care il contine pe nod
{
  if(T[nod] == 0)
        return nod;
    else
    {
        int x = Rad(T[nod]);
        T[nod] = x;
        return x;
    }
}
void Kruskal()
{

  int k=0,r1,r2;
  do{
    do{
      k++;
      r1=Rad(L[k].x);
      r2=Rad(L[k].y);
    }while(r1==r2 && k<=m); // nodurile fac parte din acelasi arbore

    //selectam muchia
    nr_muchii++;
    sol[nr_muchii][0]=L[k].x;
    sol[nr_muchii][1]=L[k].y;
    cost+=L[k].c;

    //subordonam arborele cu inaltime mai mica varfului arborelui cu inaltime mai mare
    if (H[r1]==H[r2])
    {
      T[r1]=r2;
      H[r2]++;
    }
    else
      if (H[r1]<H[r2])  T[r1]=r2;
      else T[r2]=r1;
  }while( nr_muchii<n-1);
 g<<cost<<'\n'<<n-1<<'\n';

}
int main()
{
    citire();

//  ordonam vectorul muchiilor
    sort(L+1,L+m+1,ord);

    Kruskal();

    for(int i=1;i<=nr_muchii;i++) g<<sol[i][0]<<" "<<sol[i][1]<<'\n';
    g.close();
    return 0;
}