const MAX = 400005;
type vec = record
       x, y, cost : longint;
     end;
var T, SOL : array[0 .. MAX] of longint;
    P : array[0 .. MAX] of vec;
    i, N, M, solution : longint ;
    Bufin : array[1 .. 1 shl 17] of char;

    procedure quicksort (st : longint ; dr : longint ) ;
        var min, max, mij : longint ;
            temp : vec;

        begin
            mij := P[st + random ( ( dr - st ) div 2 )].cost ;
            min := st ; max := dr ;
            while ( min <= max ) do begin
                while ( P[min].cost < mij ) do
                    inc ( min ) ;
                while ( P[max].cost > mij ) do
                    dec ( max ) ;
                if ( min <= max ) then
                    begin
                        temp := P[min] ;
                        P[min] := P[max] ; inc ( min ) ;
                        P[max] := temp ; dec ( max ) ;
                    end;
            end ; //until min > max ;

            if ( st < max ) then
                quicksort ( st, max ) ;
            if ( dr > min ) then
                quicksort ( min, dr ) ;
        end ;

    function search (x : longint) : longint;
        begin
            if x <> T[x] then
                T[x] := search (T[x]);
            search := T[x];
        end;
    procedure reunion (x, y : longint);
        begin
            T[search (x)] := search (y);
        end;

    begin {ala principal}
        assign (input, 'apm.in'); reset (input);
        SetTextBuf (input, Bufin);

        readln (N, M);
        for i := 1 to M do
            readln (P[i].x, P[i].y, P[i].cost);
        for i := 1 to N do
            T[i] := i;
        quicksort (1, M);
        for i := 1 to M do
            if search (P[i].x) <> search (P[i].y) then
                begin
                    inc (solution, P[i].cost); reunion (P[i].x, P[i].y);
                    inc (SOL[0]); SOL[ SOL[0] ] := i;
                end;
        assign (output, 'apm.out'); rewrite (output);
        writeln (solution); writeln (N - 1);
        for i := 1 to N - 1 do
            writeln (P[SOL[i]].x, ' ', P[SOL[i]].y);
        close (input); close (output);
    end.