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

var v:array [1..400000] of muchie;
    aux:muchie;
    i, j, k, n, m, p, cost:longint;
    con:array [1..200000] of longint;
    much:array[1..200000] of longint;
    f, g:text;

begin
assign (f, 'apm.in'); reset (f);
assign (g, 'apm.out'); rewrite (g);
readln (f, n, m);
for i := 1 to m do
  begin
  readln (f, v[i].x, v[i].y, v[i].c);
  end;

for i := 1 to m-1 do
  begin
  for j := i to m do
    begin
    if v[i].c > v[j].c then
      begin
      aux:= v[i]; v[i] := v[j]; v[j]:=aux;
      end;
    end;
  end;

for i := 1 to n do con[i] := i;

k:=0;
i:=1;
while (i <= m) and (k<n-1) do
  begin
  if con[v[i].x] <> con[v[i].y] then
    begin
    k:=k+1;
    cost:=cost+v[i].c;
    much[k]:=i;
    p:=con[v[i].x];
    for j := 1 to n do begin if con[j]=p then con[j] := con[v[i].y]; end;
    end;
  i:=i+1;
  end;

{for i := 1 to m do
  begin
  writeln (v[i].x, ' ', v[i].y, ' ', v[i].c);
  end;
}

writeln (g, cost);
writeln (g, n-1);
for i := 1 to k do
  begin
  writeln (g, v[much[i]].x, ' ', v[much[i]].y);
  end;

close (f);
close (g);
end.