program infoarena;
var f,g:text;
type muchie=record
     x,y,cost:integer;
     end;
var v,a:array[1..400000] of muchie;
    l:array[1..400000] of integer;
    p,q,y,contor,ct,i,k,m,n,j:integer;
function divide(p,q:integer):integer;
        var st,dr:integer; x:muchie;
        begin
        st:=p;dr:=q;x:=v[p];
        while st<dr do
         begin
         while (st<dr) and (v[dr].cost>x.cost) do dec(dr);
         v[st]:=v[dr];
         while (st<dr) and (v[st].cost<x.cost) do inc(st);
         v[dr]:=v[st];
         end;
         v[st]:=x;divide:=st;
         end;

procedure qsort(p,q:integer);
        var m:integer;
        begin
        m:=divide(p,q);
        if m-1>p then qsort(p,m-1);
        if m+1<p then qsort(m+1,q);
        end;

begin
assign(f,'apm.in');reset(f);
assign(g,'apm.out');rewrite(g);
contor:=0;
readln(f,n,m);
for i:=1 to m do readln(f,v[i].x,v[i].y,v[i].cost);
qsort(1,m);
for i:=1 to m do l[i]:=i;
k:=0;p:=1;
while k<n-1 do begin
               if l[v[p].x]<>l[v[p].y] then begin
               inc(k);
               inc(contor);
               a[contor]:=v[p];
               ct:=ct+v[p].cost;
               for j:=1 to n do
               if l[j]=l[v[p].y] then l[j]:=l[v[p].x]; end;
               inc(p);
               end;
writeln(g,ct);
writeln(g,contor);
for i:=1 to contor do writeln(g,a[i].x,' ',a[i].y);
close(g);
end.