type muchie =record
        x,y,c:longint;
             end;
var v:array[1..400001] of longint;
    viz:array[1..200001] of longint;
    u:array[1..400001] of muchie;
    nr,lv,vv,w,j,n,m,i,x:longint;
    ct:int64;
    aux:muchie;
procedure reconstituire_heap(i:longint);
   var s,d,max:longint;
   begin
     s:=2*i; d:=2*i+1;
     max:=i;
     if (s<=m)and(u[s].c>u[i].c) then max:=s;
     if (d<=m)and(u[d].c>u[max].c) then max:=d;
     if max<>i then
        begin
          aux:=u[i]; u[i]:=u[max]; u[max]:=aux;
          reconstituire_heap(max);
        end;
   end;
procedure creare_heap;
   begin
     for i:=m div 2 downto 1 do reconstituire_heap(i);
   end;
procedure heap_sort;
   begin
     creare_heap; x:=m;
     for i:=x downto 2 do
       begin
         aux:=u[1]; u[1]:=u[i]; u[i]:=aux;
         dec(m);
         reconstituire_heap(1);
       end;
   end;

begin
assign(input,'apm.in'); reset(input);
assign(output,'apm.out'); rewrite(output);
readln(n,m);
for i:=1 to m do readln(u[i].x,u[i].y,u[i].c);
heap_sort;
for i:=1 to n do viz[i]:=i;
ct:=u[1].c; viz[u[1].x]:=u[1].y;
v[1]:=1; lv:=1; nr:=2;
i:=2;
while nr<n do
  begin
    if viz[u[i].x]<>viz[u[i].y] then
       begin
         inc(nr);ct:=ct+u[i].c;
         inc(lv); v[lv]:=i;
         vv:=viz[u[i].x]; w:=viz[u[i].y];
         for j:=1 to n do if viz[j]=w then viz[j]:=vv;
       end;
    inc(i);
  end;
writeln(ct);
writeln(lv);
for i:=1 to lv do writeln(u[v[i]].x,' ',u[v[i]].y);
close(input); close(output);
end.