{Arbore partial de cost minim}

type    adresa  = ^nod;
        nod     = record inf, cst: integer; adr: adresa; end;
        elem    = record x,y,c: integer; end;
        list    = array [1..200] of elem;


var     n,m,cost     : longint;
       {p       : array [1..200] of adresa;}
        t       : array [1..200] of longint;
        uz      : array [1..200] of byte;
        muchii  : list;


function  tata       (x:longint):longint;
var     tx           : longint;
begin
tx := x;
while (t[tx]>0) do tx := t[tx];
tata := tx;
end;

procedure join       (x,y:longint);
var     tx,ty        : longint;
begin
tx := tata(x);
ty := tata(y);
if t[tx] < t[ty] then
   begin
   t[tx] := t[tx] + t[ty];
   t[y] := tx;
   end
else
   begin
   t[ty] := t[tx] + t[ty];
   t[x] := ty;
   end;
end;

function  legat      (x,y:longint):boolean;
var     tx,ty        : longint;
begin
tx := tata(x);
ty := tata(y);
if (tx = ty) then
   legat := true
else
   legat := false;
end;


procedure       rezolva;
        var
        i,count : longint;
        begin
        count := 0;
        i     := 1;
        cost  := 0;
        repeat
         if not legat (muchii[i].x, muchii[i].y) then
            begin
            join (muchii[i].x, muchii[i].y);
            inc(count);
            cost := cost + muchii[i].c;
            uz[i]:= 1;
            end;
         inc (i);
        until count = n-1;
        end;

procedure       citire;
        var
        i,j     : longint;
        x,y,c   : integer;
        q       : adresa;
        f       : text;
        begin
        assign(f,'apm.in');
        reset(f);
        readln(f,n,m);
        for i:=1 to n do t[i] := -1;
        for i:=1 to m do
            begin
            readln(f,x,y,c);
            {
            new(q);
            q^.inf := y; q^.cst := c;
            q^.adr := p[x];
            p[x]   := q;
            }
            muchii[i].x := x;
            muchii[i].y := y;
            muchii[i].c := c;
            end;
        close(f);
        end;

procedure       scrie;
var             f: text;
                i: longint;
begin
assign  (f,'apm.out');
rewrite (f);
writeln (f,cost);
writeln (f,n-1);
for i:=1 to m do
    if (uz[i] = 1) then
       writeln (f, muchii[i].x, ' ', muchii[i].y);
close   (f);
end;

procedure       QuickSort(var A: List; Lo, Hi: Integer);

procedure       Sort(l, r: Integer);
        var
        i, j    : integer;
        x, y    : elem;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i].c < x.c do i := i + 1;
    while x.c < a[j].c do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin {QuickSort};
  Sort(Lo,Hi);
end;

begin
 citire;
 QuickSort(muchii,1,m);
 rezolva;
 scrie;
end.