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:longint;
    ct:int64;
procedure pivot(s,d:longint; var mi:longint);inline;
   var ii,jj,pi,pj,au:longint;
       aux:muchie;
   begin
     ii:=s; jj:=d; pi:=0; pj:=1;
     while ii<jj do
       begin
         if u[ii].c>u[jj].c then
           begin
             aux:=u[ii]; u[ii]:=u[jj]; u[jj]:=aux;
             au:=pi; pi:=pj; pj:=au;
           end;
         ii:=ii+pi; jj:=jj-pj;
       end;
     mi:=ii;
   end;

procedure sort(s,d:longint); inline;
   var mi:longint;
   begin
     if s<d then
       begin
         pivot(s,d,mi);
         sort(s,mi-1); sort(mi+1,d);
       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);
sort(1,m);
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.