type op=record
         a,b,c:integer;
     vek=array[1..500000]of op;
     vek2=array[1..100000]of longint;
var v,v1:vek;
    f:text;
    i,j,k,l,n,m,p:longint;
    cs:vek2;
procedure min(v:vek;var d: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 atrak(var v,v1:vek;j:longint;var p:longint);
 begin
  v1[p]:=v[j];
  for k:=j to m-1 do
   begin
    v[k]:=v[k+1];
   end;
  dec(m);
  inc(p);
 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;
   atrak(v,v1,j,p);
   inc(i);
  end;
 ossz:=0;
 for i:=1 to p do inc(ossz,v1[i].c);
 assign(f,'apm.out');
 rewrite(f);
 writeln(f,ossz);
 writeln(f,n-1);
 for i:=1 to p do
  writeln(f,v1[i].a,' ',v1[i].b);
 close(f);
end.