program _apm;
type
        _tip1 = record x, y ,c : longint; end;
        _vector1 = array [1..400000] of _tip1;
        _vector2 = array [1..200000] of longint;
        _buffer  = array [1..1 shl 22] of char;
var
        l : _vector1;
        u : _vector2;
        buf : _buffer;
        n ,m ,ct : longint;

procedure _scanf; forward;
procedure _swap(var a ,b : _tip1); forward;
procedure _qsort(st, dr : longint); forward;
function  _rad(nod : longint) : longint; forward;
procedure _greedy; forward;
procedure _printf; forward;

procedure _scanf;
var
        i : longint;
begin
        assign(input,'apm.in'); reset(input); settextbuf(input, buf);
        readln(n, m);

        for i := 1 to m do readln(l[i].x ,l[i].y, l[i].c);
end;

procedure _swap(var a ,b : _tip1);
var
        c : _tip1;
begin
        c := a; a := b; b := c;
end;

procedure _qsort(st ,dr : longint);
var
        i ,j ,m : longint;
begin
i := st; j := dr; m := l[(i + j) div 2].c;
while (i < j) do
begin
        while (l[i].c < m) do i := i + 1;
        while (l[j].c > m) do j := j - 1;
        if (i <= j) then
        begin
                _swap(l[i], l[j]);
                i := i + 1;
                j := j - 1;
        end;
end;
if (i < dr) then _qsort(i ,dr);
if (j > st) then _qsort(st, j);
end;

function _rad(nod : longint) : longint;
begin
        if u[nod] = nod then u[nod] := nod else
        u[nod] := _rad(u[nod]);
        _rad := u[nod];
end;

procedure _greedy;
var
        j ,i ,k ,a, b : longint;
begin
        for i := 1 to n do u[i] := i;
        k := 0;
        i := 1;
        a := l[i].x;
        b := l[i].y;
        while (k < n - 1) do
        begin
                while (i < m) and (_rad(a) = _rad(b)) do
                begin
                        i := i + 1;
                        a := l[i].x;
                        b := l[i].y;
                end;
                if (a <> b) then
                begin
                        k := k + 1;
                        l[k] := l[i];
                        ct := ct + l[i].c;
                        u[_rad(a)] := _rad(b);
                end;
        end;
end;

procedure _printf;
var
        i : longint;
begin
        assign(output,'apm.out'); rewrite(output); settextbuf(output, buf);
        write(ct,#10,n - 1,#10);
        for i := 1 to n - 1 do write(l[i].x,#32,l[i].y,#10);
end;

begin
_scanf;
_qsort(1, m);
_greedy;
_printf;
end.