const f = 'apm.in'; g = 'apm.out';

type muchie = record
        x, y, cost : longint;
end;

type vector= array[0..400067] of muchie;

var

    MC : vector;
    aux : muchie;
    n, m, i, j : longint;
    sf : longint;
    TREE : array[0..200067] of longint;
    APM : array[0..200067] of muchie;
    buf, buf1 : array[1..1 shl 17 ] of char;

procedure quick( var a : vector; st: longint; dr : longint);
    var
        min, max, mij : longint;
    begin
        min := st;
        max := dr;
        mij := a[(st + dr) div 2].cost;
        repeat
            while (a[min].cost < mij) do inc( min );
            while (a[max].cost > mij) do dec( max );
            if (min <= max) then begin
                aux := a[min];
                a[min] := a[max];
                a[max] := aux;
                inc( min );
                dec( max );
            end;
        until (min >= max);
        if (st <= max) then quick(a, st, max);
        if (min <= dr) then quick(a, min, dr);
    end;


function grupa( i : longint ) : longint;
    var
        rez : longint;
    begin

        if Tree[i] = i then
                rez := i
        else
            rez := grupa(Tree[i]);
        Tree[i] := rez;
        grupa := rez;

    end;

procedure kruskal();
    var
        x, y, i, costmin : longint;
    begin

        quick(MC, 1, m );

        costmin := 0; j := 1; // init costul min cu 0 si contorul pt muchii cu 1;
        for i := 1 to n do TREE[i] := i; // init arb disjuncti;

        for i := 1 to n-1 do begin // pt fiecare nod (mai putin ultimul)
            while grupa(MC[j].x) = grupa(MC[j].y) do inc( j );//cat timp nu exista arb disjuncti
            Tree[grupa(MC[j].x)] := grupa(MC[j].y); // unesc arborii
            costmin := costmin + MC[j].cost; // adaug costul muchie la costul minim
            APM[i] := MC[j]; // adaug muchia la vectorul de solutii;
        end;

        writeln( costmin );

    end;

begin
    assign( input,f ); reset( input );
    assign( output,g ); rewrite( output );
    settextbuf( input,buf );
    settextbuf( output,buf1 );
    readln( n, m );

    for i := 1 to m do
        readln(MC[i].x, MC[i].y, MC[i].cost);

    kruskal();

    writeln( n-1 );
    for i := 1 to n-1 do writeln( APM[i].x,' ',APM[i].y );
end.