type op=record
          a,b,c:integer;
         end;
     vek=array[1..20000]of op;
     vek2=array[1..30000]of longint;
var v,v1:vek;
    f:text;
    i,j,k,l,n,m,p,ossz:longint;
    cs:vek2;
procedure min(v:vek;var d:longint);
 var i,mini:longint;
  begin
   mini:=v[1].c;
   d:=1;
   for i:=2 to n do
    if v[i].c<mini then
     begin
      mini:=v[i].c;
      d:=i;
     end;
  end;
procedure kivesz(var v:vek;j:longint);
  var k:longint;
 begin
  for k:=j to m-1 do
   begin
    v[k]:=v[k+1];
   end;
  dec(m);

 end;

begin
 assign(f,'apm.in');
 reset(f);
 readln(f,n,m);
 for i:=1 to n do
   readln(f,v[i].a,v[i].b,v[i].c);
 close(f);
 for i:=1 to n do cs[i]:=i;
 p:=1;
 while i<=m do
  begin
   min(v,j);
   if cs[v[j].a]<>cs[v[j].b] then
   for k:=1 to n do
    begin
     l:=cs[v[j].b];
     if (cs[k]=l) then cs[k]:=cs[v[j].a];
    end;
   kivesz(v,j);
   inc(i);
  end;
 ossz:=0;
 for i:=1 to p do ossz:=ossz+v[i].c;
 assign(f,'apm.out');
 rewrite(f);
 writeln(f,ossz);
 writeln(f,n-1);
 for i:=1 to p do
  writeln(f,v[i].b,' ',v[i].a);
 close(f);
end.