#include <fstream>

#define NMAX 200002

#define MMAX 400002



using namespace std;

ifstream fin("apm.in");

ofstream fout("apm.out");

struct Muchie{int x, y, cost;

              //Overloading operators

              friend bool operator < (Muchie a, Muchie b);

              friend bool operator > (Muchie a, Muchie b);

              friend bool operator >= (Muchie a, Muchie b);

              friend bool operator <= (Muchie a, Muchie b);

             };

bool operator < (Muchie a, Muchie b){

    return a.cost<b.cost;

}

bool operator > (Muchie a, Muchie b){

    return a.cost>b.cost;

}

bool operator >= (Muchie a, Muchie b){

    return a.cost>=b.cost;

}

bool operator <= (Muchie a, Muchie b){

    return a.cost<=b.cost;

}



int n,m,nrsel,costtotal;

Muchie H[MMAX];

Muchie A[MMAX];

int tata[NMAX], h[NMAX];

int Find(int x);    ///Returneaza radacina din care face parte x

void Union(int x, int y);///Reuneste arborele lui x cu arborele lui y

void creare();

void afisare();

void combinare(int n, Muchie H[], int poz);

Muchie extrageMin(int &n, Muchie H[]);



int main(){Muchie mmin; int cx,cy;

    // citire(n, H);

    creare();//Heapul este creat

    while(nrsel<n-1){

        mmin = extrageMin(m, H);

        cx = Find(mmin.x);

        cy = Find(mmin.y);

        if(cx != cy){

            nrsel++;

            A[nrsel] = mmin;

            costtotal += mmin.cost;

            Union(cx,cy);

        }

    }

    afisare();

    return 0;

}



void afisare(){int i;

    fout<<costtotal<<'\n';

    fout<<n-1<<'\n';

    for(i=1;i<n;i++)

        fout<<A[i].y<<' '<<A[i].x<<'\n';

    fout.close();

}



void inserare(int& n, Muchie H[], Muchie x){int tata, fiu;

    fiu=++n; tata=fiu/2;

    while(tata && H[tata]>x){

        H[fiu]=H[tata];

        fiu=tata;

        tata=fiu/2;

    }

    H[fiu]=x;

}



void combinare(int n, Muchie H[], int poz){Muchie x=H[poz];int fiu, tata;

    tata=poz;

    fiu=2*tata;

    while(fiu<=n){

        if(fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;

        if(x <= H[fiu]) break;

        H[tata]=H[fiu];

        tata=fiu;

        fiu=2*tata;

    }

    H[tata]=x;

}



void creare(){int i;

    fin>>n>>m;

    for(i=1; i<=m; i++) fin>>H[i].x>>H[i].y>>H[i].cost;

    for(i=m/2; i>0; i--) combinare(m, H, i);

}



Muchie extrageMin(int &n, Muchie H[]){Muchie minim=H[1];

    H[1]=H[n--];

    combinare(n,H,1);

    return minim;

}



int Find(int x){int aux, rad;

    rad = x;

    while(tata[rad]) rad = tata[rad];

    ///Compresia drumului

    while(tata[x]){

        aux = tata[x];

        tata[x] = rad;

        x = aux;

    }

    return rad;

}



void Union(int x,int y){

    x = Find(x); y = Find(y);

    if(h[x]<h[y]) tata[x] = y;

    else{

        tata[y] = x;

        if(h[x] == h[y]) h[x]++;

    }

    ///O(1)

}