#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
{
    while (T[nod]) nod=T[nod];
    return nod;
}
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 !! stim sigur ca putem construi arbore
    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;
}