var f:text;
    n,m,aux,costul,muchie,r:int64;
    i:integer;
    m1,m2,cost,nod,afis1,afis2:array[1..400000] of int64;
procedure quick(st,dr:int64);
var i,ii,j,jj:int64;
begin
i:=st;
j:=dr;
ii:=0;
jj:=-1;
while i<j do        //aici ba ai mic
 begin
  if cost[i]>cost[j] then
   begin
    aux:=cost[i];
    cost[i]:=cost[j];
    cost[j]:=aux;
    aux:=m1[i];
    m1[i]:=m1[j];
    m1[j]:=aux;
    aux:=m2[i];
    m2[i]:=m2[j];
    m2[j]:=aux;
    aux:=i;
    i:=-j;
    j:=-aux;
   end;
  i:=i+ii;
  j:=j+jj;
 end;
if st<dr then
 begin
  quick(st,i-1);
  quick(i+1,dr);
 end;
end;

begin
assign(f,'apm.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
    readln(f,m1[i],m2[i],cost[i]);
close(f);
quick(1,n);
nod[1]:=1;
for i:=1 to n do
 nod[i]:=i;
for i:=1 to n do
 begin
 if nod[m1[i]]<>nod[m2[i]] then
  if nod[m1[i]]>nod[m2[i]] then
   begin
   nod[m1[i]]:=nod[m2[i]];
   nod[m2[i]]:=nod[m2[i]];
   costul:=costul+cost[i];
   inc(muchie);
   inc(r);
   afis1[r]:=m1[i];
   afis2[r]:=m2[i];
   end
    else
   begin
   nod[m1[i]]:=nod[m1[i]];
   nod[m2[i]]:=nod[m1[i]];
   costul:=costul+cost[i];
   inc(muchie);
   inc(r);
   afis1[r]:=m1[i];
   afis2[r]:=m2[i];
   end;
 end;
assign(f,'apm.out');
rewrite(f);
writeln(f,costul);
writeln(f,muchie);
for i:=1 to r do
writeln(f,afis1[i],' ',afis2[i]);
close(f);
end.