program apm;
type el=record
        x,y,c:longint;
        end;
var bufin,bufout:array[1..1 shl 17] of char;
    f,g:text;
    n,m,s,k,i,a,b:longint;
    t,nr:array[1..200005] of longint;
    v:array[1..400005] of el;
function tata(nod:longint):longint;
  begin
    if t[nod]<0 then
                tata:=nod
                else
                begin
                  t[nod]:=tata(t[nod]);
                  tata:=t[nod];
                end;
  end;
function pivot(st,dr:longint):longint;
var di,dj,i,j,auxx:longint;
    aux:el;
  begin
    i:=st;
    j:=dr;
    di:=0;
    dj:=1;
    while i<j do
      begin
        if v[i].c>v[j].c then
                          begin
                            aux:=v[i];
                            v[i]:=v[j];
                            v[j]:=aux;
                            auxx:=di;
                            di:=dj;
                            dj:=auxx;
                          end;
        i:=i+di;
        j:=j-dj;
      end;
    pivot:=i;
  end;
procedure quicksort(st,dr:longint);
var p:longint;
 begin
   if st<dr then
            begin
              p:=pivot(st,dr);
              quicksort(st,p-1);
              quicksort(p+1,dr);
            end;
 end;
begin
    assign(f,'apm.in');
    assign(g,'apm.out');
    settextbuf(f,bufin);
    settextbuf(g,bufout);
    reset(f);
    rewrite(g);
    readln(f,n,m);
    for i:=1 to m do
      begin
        readln(f,v[i].x,v[i].y,v[i].c);
      end;
  quicksort(1,m);
    k:=0;
    for i:=1 to n do
      t[i]:=-1;
    for i:=1 to m do
      begin
        a:=tata(v[i].x);
        b:=tata(v[i].y);
        if a<>b then
                begin
                  t[b]:=a;
                  k:=k+1;
                  nr[k]:=i;
                  s:=s+v[i].c;
                end;
      end;
   writeln(g,s);
   writeln(g,n-1);
   for i:=1 to k do
     writeln(g,v[nr[i]].x,' ',v[nr[i]].y);
   close(f);
   close(g);
end.