var x,y:array[1..400000]of longint;
v:array[1..400000]of integer;
rang,sol,comp:array[1..200000]of longint;
i,n,m,cost,k:longint;


procedure sort(i,j:longint);
var st,dr,aux,mij:longint;
begin
st:=i; dr:=j;
mij:=v[(st+dr)div 2];
repeat
while v[st]<mij do inc(st);
while v[dr]>mij do dec(dr);
if st<=dr then begin
   aux:=v[st]; v[st]:=v[dr]; v[dr]:=aux;
   aux:=x[st]; x[st]:=x[dr]; x[dr]:=aux;
   aux:=y[st]; y[st]:=y[dr]; y[dr]:=aux;
   inc(st); dec(dr);
   end;
until st>dr;
if st<j then sort(st,j);
if i<dr then sort(i,dr);
end;

function find(nod:longint):longint;
var rad,a:longint;
begin
rad:=nod;
while rad<>comp[rad] do rad:=comp[rad];
while nod<>comp[nod] do begin
      a:=comp[nod];
      comp[nod]:=rad;
      nod:=a;
end;
find:=rad;
end;

procedure unesc(x,y:longint);
begin
if rang[x]>rang[y] then comp[y]:=x
                   else comp[x]:=y;
if rang[x]=rang[y] then inc(rang[y]);
end;



begin
assign(input,'apm.in');reset(input);
assign(output,'apm.out');rewrite(output);

read(n,m);
for i:=1 to m do read(x[i],y[i],v[i]);

for i:=1 to n do begin
    comp[i]:=i;
    rang[i]:=1;
end;

sort(1,m);

k:=0; i:=1;  cost:=0;
while k<n-1 do begin
      if find(x[i])<>find(y[i]) then begin
         inc(k);
         sol[k]:=i;
         cost:=cost+v[i];
         unesc(x[i],y[i]);
      end;
      inc(i);
end;

writeln(cost);
writeln(n-1);
for i:=1 to n-1 do writeln(x[sol[i]],' ',y[sol[i]]);
close(output);
end.