program dsdl;
type mi=record
    x,y,c:longint;
    end;
var f,g:text;
  n,i,j,suma,k,m,a,b,numar:longint;
  ok:boolean;
  aux:mi;
  v,cr:array[1..400000] of mi;
  nr,t:array[1..400000] of longint;
function tata(nod:longint):longint;
  begin
    while t[nod]<>0 do
      nod:=t[nod];
    tata:=nod;
  end;
procedure sortare;
begin
 repeat
 ok:=true;
   for i:=1 to m-1 do
     if v[i].c>v[i+1].c then
        begin
        aux:=v[i];
        v[i]:=v[i+1];
        v[i+1]:=aux;
        ok:=false;
        end;
 until ok;
end;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
  readln(f,n,m);
    for i:=1 to m do
      begin
        read(f,v[i].x,v[i].y,v[i].c);
      end;
  sortare;
  k:=1;
  repeat
   while tata(v[k].x)=tata(v[k].y) do
     k:=k+1;
   numar:=numar+1;
   suma:=suma+v[k].c;
   cr[numar].x:=v[k].x;
   cr[numar].y:=v[k].y;
     if nr[v[k].x]=nr[v[k].y] then
       begin
        t[v[k].x]:=v[k].y;
        nr[v[k].y]:=nr[v[k].y]+1;
       end
       else
         if nr[v[k].x]<nr[v[k].y] then
           t[v[k].x]:=v[k].y
           else
           t[v[k].y]:=v[k].x;
       k:=k+1;
  until (numar=n-1);
  writeln(g,suma);
  writeln(g,n-1);
    for i:=1 to numar do
      writeln(g,v[i].y,' ',v[i].x);
close(f);
close(g);
end.