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,io:array[1..200000] of muchie;
t,rang,rt:array[1..200000] of longint;
nod:muchie;
procedure insheap;
var aux:muchie;
begin
j:=i;
while (j div 2<>0)and(v[j div 2].c>v[j].c) do
   begin
   aux:=v[j];
   v[j]:=v[j div 2];
   v[j div 2]:=aux;
   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;
while i<>0 do
   begin

   nod:=v[1];
   restheap;
   dec(l);
   t1:=cauta_tata(nod.x);
   t2:=cauta_tata(nod.y);
   if t1<>t2 then
   begin
   io[i]:=nod;
   dec(i);
   c:=c+nod.c;
   if rang[nod.x]=rang[nod.y] then
      begin
      inc(rang[nod.y]);
      t[t2]:=t1;
      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:=1 to n-1 do
    writeln(g,io[i].x,' ',io[i].y);





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