type muchie =record
        x,y,c:integer;
             end;
var v:array[1..200000] of 1..200000;
    viz:array[1..200000] of 0..1;
    u:array[1..200000] of muchie;
    j,n,m,i,ct:longint;
procedure sort(s,d:longint);
   var a,b,ia:longint;
       t:muchie;
   begin
     a:=s; b:=d;
     repeat
       while u[a].c<u[b].c do dec(b);
       t:=u[a]; u[a]:=u[b]; u[b]:=t;
       inc(a); ia:=1;
       if a<b then
         begin
           while u[a].c<u[b].c do inc(a);
           t:=u[a]; u[a]:=u[b]; u[b]:=t;
           dec(b); ia:=0;
         end;
     until a>=b;
     if s<a-ia then sort(s,a-ia);
     if d>a-ia+1 then sort(a-ia+1,d);
   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);
ct:=u[1].c; viz[u[1].x]:=1; viz[u[1].y]:=1;
v[1]:=1;
for i:=3 to n do
   begin
     j:=1; while (viz[u[j].x]=viz[u[j].y]) do inc(j);
     if viz[u[j].x]=1 then
          begin
            viz[u[j].y]:=1;
            ct:=ct+u[j].c;
            v[i-1]:=j;
          end
                       else
          begin
            viz[u[j].x]:=1;
            ct:=ct+u[j].c;
            v[i-1]:=j;
          end;
   end;
writeln(ct);
writeln(n-1);
for i:=1 to n-1 do writeln(u[v[i]].x,' ',u[v[i]].y);
close(input); close(output);
end.