program apm;
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 byte;
ok:boolean;
v:array[1..400000] of muchie;
gr,sol:array of longint;
n,m,i,l,u,cost,gr1,nrsol:longint;
function grupa(a:longint):longint;
begin
if gr[a]=a then
begin
grupa:=a;
exit;
end;
gr[a]:=grupa(gr[a]);
grupa:=gr[a];
end;
procedure reuniune(a,b:longint);
begin
gr[grupa(a)]:=grupa(b);
end;
function pivot(st,dr:longint):longint;
var d,r,ri:longint;
aux:muchie;
begin
d:=st;
r:=dr;
ri:=1;
while d<r do
   begin
   if v[d].c>v[r].c then
      begin
      aux:=v[d];
      v[d]:=v[r];
      v[r]:=aux;
      ri:=-ri;
           end;
      if ri=-1 then
      dec(r) else
      inc(d);
   end;
   randomize;
   pivot:=r;
end;
procedure qsort(st,dr:longint);
var p:longint;
begin
if st<dr then
   begin
   p:=pivot(st,dr);
   qsort(st,p-1);
   qsort(p,dr);
   end;
end;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
read(f,n,m);
setlength(gr,n+1);
setlength(sol,n+1);
for i:=1 to n do
gr[i]:=i;
for i:=1 to m do
readln(f,v[i].x,v[i].y,v[i].c);

qsort(1,m);
nrsol:=0;
for i:=1 to m do
for i:=1 to m do
   begin
   l:=grupa(v[i].x);
   u:=grupa(v[i].y);
   if l<>u then
      begin
      reuniune(v[i].x,v[i].y);
      inc(nrsol);
      sol[nrsol]:=i;
            cost:=cost+v[i].c;
         end;
   end;
     writeln(g,cost);
   writeln(g,n-1);
   for i:=1 to n-1 do
   writeln(g,v[sol[i]].x,' ',v[sol[i]].y);
close(f);
close(g);
end.