type muchie=record
u,v,cost:longint;
end;
graf=array[1..100000]of muchie;
var g:graf;
c:array[1..100000]of longint;
i,n,m,ms,k,a,b,ct:longint;
aux:muchie;
ok:boolean;
f,h:text;

procedure divid(st,dr:longint);
 var p,i,j:longint;
 begin
 i:=st;
 j:=dr;
 p:=g[(st+dr)div 2].cost;
 while (i<=j) do
    begin
      while (g[i].cost<p) do i:=i+1;
      while (g[j].cost>p) do j:=j-1;
     if i<=j then begin
              aux:=g[i];
              g[i]:=g[j];
              g[j]:=aux;
              i:=i+1;
              j:=j-1;
              end;
    end;
    if st<j then divid(st,j);
    if dr>i then divid(i,dr);
end;

begin
assign(f,'apm.in');
reset(f);
assign(h,'apm.out');
rewrite(h);
readln(f,n,m);
for i:=1 to m do
  readln(f,g[i].u,g[i].v,g[i].cost);
divid(1,n);
for i:=1 to n do
c[i]:=i;
repeat
  ok:=true;
  for i:=1 to m-1 do
      if g[i].cost>g[i+1].cost then
         begin
         aux:=g[i];
         g[i]:=g[i+1];
         g[i+1]:=aux;
         ok:=false;
         end;
until ok;
ct:=0;
ms:=0;
k:=1;
while ms<n-1 do
begin
  while c[g[k].u]=c[g[k].v] do
    inc(k);
  ct:=ct+g[k].cost;
  ms:=ms+1;
  a:=g[k].u;
  b:=g[k].v;
  for i:=1 to n do
     if c[i]=c[a] then c[i]:=c[b];
  end;
writeln(h,ct);
writeln(h,ms);
for i:=1 to ms do
  writeln(h,g[i].v,' ',g[i].u);
close(h);
end.