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,nrs:longint;
v:array[1..400000] of muchie;
io:array[1..200000] of longint;
t,rang:array[1..200000] of longint;
nod:muchie;
function cauta_tata(a:longint):longint;
begin
if t[a]=a then
begin
cauta_tata:=a;
exit;
end;
t[a]:=cauta_tata(t[a]);
cauta_tata:=t[a];
end;
procedure reuniune(a,b:longint);
begin
t[cauta_tata(a)]:=cauta_tata(b);
end;

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;

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;
for i:=m downto 1 do
   begin

   nod:=v[i];
   t1:=cauta_tata(nod.x);
   t2:=cauta_tata(nod.y);
   if t1<>t2 then
   begin
   inc(nrs);
   io[nrs]:=i;
   c:=c+nod.c;

     reuniune(nod.x,nod.y);
      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.