#include <fstream>
#include <algorithm>
#define DIMN 200005
#define DIMM 400005
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie{
    int x, y, c;
} v[DIMM];

int N, M, Selectat[DIMN], T[DIMN], H[DIMN], Cmin;

void Citire(){

    int i;

    f >> N >> M;

    for(i=1;i<=M;i++)
        f >> v[i].x >> v[i].y >> v[i].c;

}

bool cmp( Muchie A, Muchie B ){
    if( A.c < B.c )
        return 1;
    return 0;
}

int Grupa( int NOD ){

    int grupa, r, rvechi;

    r = NOD;                                // Det reprezentantului grupei
    while( T[r] != 0 ){
        r = T[r];
    }
    grupa = r;

    r = NOD;                                // Legarea elem din drum cu reprezentantul grupei = grupa
    while( T[r] != 0 ){
        rvechi = r;
        r = T[r];                           // Nu uit  asta cu rvechi           #########
        T[rvechi] = grupa;
    }

    return grupa;

}

void Uneste( int NOD1, int NOD2 ){

    if( H[NOD1] > H[NOD2] ){                // NOD1 e mai adanc
        T[NOD2] = NOD1;                     // NOD2 leg la NOD1
    }
    else if( H[NOD1] < H[NOD2] ){           // NOD2 e mai adanc
        T[NOD1] = NOD2;                     // NOD1 leg la NOD2
    }
    else{
        T[NOD2] = NOD1;                     // La fel de adanci
        H[NOD1] ++;                         // tre sa modific H[vf]             #########
    }

}

void Rezolvare(){

    int i, x, y, m = 0;                     // m = nr de muchii alese
    Cmin = 0;

    for(i=1;i<=M;i++){

        x = v[i].x;
        y = v[i].y;

        if( Grupa(x) != Grupa(y) ){

            Cmin += v[i].c;
            Selectat[ ++m ] = i;
            Uneste( Grupa(x), Grupa(y) );   // Nu uit ca tre sa unesc Grupa(x), nu doar x cu y          ##########

            if( m == N-1 )                  // Am selectat cele N-1 muchii,
                break;                      // deci ne oprim, ca am creeat arborele
        }

    }

}

void Afisare(){

    int i;

    g << Cmin << "\n";
    g << N-1  << "\n";

    for(i=1;i<=N-1;i++)
        g << v[ Selectat[i] ].x << " " << v[ Selectat[i] ].y << "\n";

}


int main(){

    Citire();
    sort(v+1,v+M+1,cmp);
    Rezolvare();
    Afisare();

return 0;
}