program _amp;
type
        _tip1 = record x, y ,c : longint; end;
        _vector1 = array [1..200000] of _tip1;
        _vector2 = array [1..200000] of longint;
var
        l : _vector1;
        u : _vector2;
        n ,m ,ct : longint;

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

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

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

        close(f);
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;

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

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

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