program apm;
uses math;
const fi='apm.in';
      fo='apm.out';
type muchie=record
 x,y,c:longint;
 end;
var f,g:text;
bufin,bufout:array [1..65000] of char;
i,n,m,j,t1,t2,k,min1,l,c:longint;
v:array[1..400000] of muchie;
io:array[1..200000] of longint;
t,rang:array[1..200000] of longint;
nod:muchie;
procedure insheap;
var aux:muchie;
el:longint;
begin
j:=i div 2;
el:=i;
while (j<>0)and(v[j].c>v[el].c) do
   begin
   aux:=v[j];
   v[j]:=v[el];
   v[el]:=aux;
   el:=j;
   j:=j div 2;
   end;
end;
function cauta_tata(x:longint):longint;
begin
while t[x]<>x do
    x:=t[x];
    cauta_tata:=x;
end;

procedure restheap;
var aux:muchie;
begin
aux:=v[1];
v[1]:=v[l+1];
v[l+1]:=aux;
k:=1;
while (k*2<=l)and(v[k].c>min(v[k*2].c,v[k*2+1].c)) do
begin
min1:=k*2;
if (k*2+1<=l)and(v[k*2].c>v[k*2+1].c) then
min1:=k*2+1;
if min1>l then
   break;
aux:=v[min1];
v[min1]:=v[k];
v[k]:=aux;
k:=min1;
end;

end;


begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
read(f,n,m);
for i:=1 to m do
   begin
   read(f,v[i].x,v[i].y,v[i].c);
   insheap;
   end;
   for i:=1 to n do
       t[i]:=i;
       l:=m-1;
       i:=n-1;
       c:=0;

for i:=1 to m do
   begin
   restheap;
   dec(l);
   end;
   l:=m;
   i:=n-1;
while i<>0 do
   begin

   nod:=v[l];
   dec(l);
   t1:=cauta_tata(nod.x);
   t2:=cauta_tata(nod.y);
   if t1<>t2 then
   begin
   io[i]:=l+1;
   dec(i);
   c:=c+nod.c;
   if rang[nod.x]=rang[nod.y] then
      begin
      inc(rang[nod.y]);
      t[t1]:=t2;
      end
   else
   if rang[nod.x]<rang[nod.y] then
       t[t1]:=t2
       else
       t[t2]:=t1;
       end;
   end;
writeln(g,c);
writeln(g,n-1);
for i:=n-1 downto 1 do
    writeln(g,v[io[i]].x,' ',v[io[i]].y);





   close(f);
close(g);
end.