type muchie=record
        c,a,b:longint;
end;
var     f,g:text;
        v:array[-1..400010] of muchie;
        bufin,bufout:array[1..65000] of byte;
        n,m,i,x,y,z,j,sum,c1,c2:longint;
        p,sol:array[-1..400010] of longint;

function pivot(st,dr:longint):longint;
var     m,i:longint;
        aux:muchie;
begin
        i:=1;
        m:=st+random(dr-st)+1;
        aux:=v[m]; v[m]:=v[st];  v[st]:=aux;
        while st<dr do begin
                if v[st].c>v[dr].c then begin
                        aux:=v[dr]; v[dr]:=v[st];  v[st]:=aux;
                        i:=-i;
                end;
                if i>0 then dec(dr) else inc(st);
        end;
        pivot:=st;
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+1,dr);
        end;
end;

function varf(n:longint):longint;
begin
        while p[n]<>0 do n:=p[n];
        varf:=n;
end;

begin
        assign(f,'apm.in');
        assign(g,'apm.out');
        reset(f);
        rewrite(g);
        settextbuf(f,bufin);
        settextbuf(g,bufout);
        readln(f,n,m);
        for i:=1 to m do
                readln(f,v[i].c,v[i].b,v[i].c);
        qsort(1,m);
        j:=n;
        i:=0;
        sum:=0;
        while j<>1 do begin
                inc(i);
                c1:=varf(v[i].a);
                c2:=varf(v[i].b);
                if c1<>c2 then begin
                        p[c2]:=c1;
                        sum:=sum+v[i].c;
                        sol[j]:=i;
                        dec(j);
                end;
        end;
        writeln(g,sum);
        writeln(g,n-1);
        for i:=2 to n do writeln(g,v[sol[i]].a,' ',v[sol[i]].b);
        close(g);


end.