#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(int i,int j)
//{return (L[i].c<L[j].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();
}

void poz(int li, int ls, int &k)
{
    int i,j,vi,aux,vj;
    muchie maux;
    i=li; j=ls; vi=0; vj=1;
    while(i<j)
    {
        if(L[i].c>L[j].c)
        {
            maux=L[i];L[i]=L[j];L[j]=maux;
            aux=vi;vi=vj;vj=aux;
        }
        i=i+vi;  j=j-vj;
    }
    k=i;
}
void quicksort(int li, int ls)
{
    int k=0;
    if(li<ls)
    {
        poz(li,ls,k);
        quicksort(li,k-1);
        quicksort(k+1,ls);
    }
}
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
    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);
    quicksort(1,m);
    Kruskal();
    for(int i=1;i<=nr_muchii;i++) g<<sol[i][0]<<" "<<sol[i][1]<<'\n';
    g.close();
    return 0;
}