program dsdl;
type mi=record
    x,y,c:longint;
    end;
var f,g:text;
  n,i,j,suma,k,m,a,b:longint;
  ok:boolean;
  aux:mi;
  v:array[1..400022] of mi;
  nr,t:array[1..400022] of longint;
function tata(nod:longint):longint;
  begin
  if t[nod]<0 then
    tata:=nod
    else
    begin
     t[nod]:=tata(t[nod]);
     tata:=t[nod];
    end;
  { if t[nod]<>0 then
     t[nod]:=tata(t[nod])
     else
     tata:=nod;  }
  end;
procedure sortare;
begin
 repeat
 ok:=true;
   for i:=1 to m-1 do
     if v[i].c>v[i+1].c then
        begin
        aux:=v[i];
        v[i]:=v[i+1];
        v[i+1]:=aux;
        ok:=false;
        end;
 until ok;
end;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
  readln(f,n,m);
    for i:=1 to m do
      begin
        read(f,v[i].x,v[i].y,v[i].c);
      end;
  sortare;
  for i:=1 to n do
  t[i]:=-1;
    for i:=1 to m do
      begin
       a:=tata(v[i].x);
       b:=tata(v[i].y);
         if a<>b then
           begin
             t[a]:=t[a]+t[b];
             t[b]:=a;
             suma:=suma+v[i].c;
             k:=k+1;
             nr[k]:=i;
           end;
      end;
    writeln(g,suma);
    writeln(g,k);
      for i:=1 to k do
         writeln(g,v[nr[i]].x,' ',v[nr[i]].y);
close(f);
close(g);
end.