type op=record
          a,b,c:integer;
         end;
     vek=array[1..20000]of op;
     vek2=array[1..20000]of longint;
var s:string;
    v,v1:vek;
    f,g: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 y:longint;
 begin
  inc(p);
  for y:=j to m-p do
   begin
    v[y]:=v[y+1];
   end;


 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;
 assign(f,'apm1.out');
 rewrite(f);
 p:=0;
 ossz:=0;
 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;
   ossz:=ossz+v[j].c;
   writeln(f,v[j].b,' ',v[j].a);
   kivesz(v,j);
   inc(i);
  end;
 close(f);
 assign(f,'apm1.out');
 reset(f);
 assign(g,'apm.out');
 rewrite(g);
 writeln(g,ossz);
 writeln(g,n-1);
 while not eof(f) do
  begin
   readln(f,s);
   writeln(g,s);
   end;
 close(f);
 close(g);
end.