type muchie= record
      x,y:longint;
      cost:integer;
      end;
const nmax=50000;
const inf=100000000;
var f,g:text;
v:array[1..5*nmax] of muchie;
c,a,b:array[1..nmax]of longint;
ct,k,x,y,i,m,j,n,z:longint;
ok:boolean;
procedure divid(st,dr:longint);
var p,i,j:longint;
aux:muchie;
begin
i:=st;
j:=dr;
p:=v[(st+dr)div 2].cost;
while (i<=j) do
   begin
     while (v[i].cost<p) do i:=i+1;
     while (v[j].cost>p) do j:=j-1;
     if i<=j then begin
             aux:=v[i];
             v[i]:=v[j];
             v[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(g,'apm.out');
rewrite(g);
readln(f,n,m);
for i:=1 to m do
   begin
     readln(f,x,y,z);
     v[i].x:=x;
     v[i].y:=y;
     v[i].cost:=z;
   end;
divid(1,m);
for i:=1 to n do
  c[i]:=i;
i:=1;
k:=0;
ct:=0;
while (i<=m) and (k<=n-1) do
     begin
     if c[v[i].x]<>c[v[i].y] then
                   begin
                   k:=k+1;
                   x:=c[v[i].x];
                   a[k]:=v[i].x;
                   y:=c[v[i].y];
                   b[k]:=v[i].y;
                   ct:=ct+v[i].cost;
                   for j:=1 to n do
                      if c[j]=x then c[j]:=y;
                   end;
     i:=i+1;
end;
writeln(g,ct);
writeln(g,k);
for i:=1 to k do
   writeln(g,a[i],' ',b[i]);
close(g);
end.