type muchie=record
u,v,cost:longint;
end;
graf=array[1..200000]of muchie;
var g:graf;
t,x,y,c:array[1..100000]of longint;
i1,i2,i3,j,i,n,m,ms,k,a,b:longint;
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);
read(f,n,m);
for i:=1 to m do
  begin
  read(f,i1,i2,i3);
  g[i].u:=i1;
  g[i].v:=i2;
  g[i].cost:=i3;
  end;
divid(1,m);

for i:=1 to n do
c[i]:=i;
ct:=0;
i:=1;
k:=0;
while (i<=m)and (k<N-1) do
begin
  if c[g[i].u]<>c[g[i].v]then
                     begin
                        k:=k+1;
                        ct:=ct+g[i].cost;
                        a:=c[g[i].u];
                        x[k]:=g[i].u;
                        b:=c[g[i].v];
                        y[k]:=g[i].v;
                        t[i]:=i;
                        for j:=1 to k do
                           begin
                           if c[x[j]]=a then c[x[j]]:=b;
                           if c[y[j]]=a then c[y[j]]:=b;
                           end;
                        end;
  i:=i+1;
  end;
writeln(h,ct);
writeln(h,k);
for i:=1 to k do
  writeln(h,y[i],' ',x[i]);
close(h);
 end.