program apm;
const nmax=100;
type muchie=record
 x,y:byte;
 cost:real;
end;
  indice=1..nmax;

var v,w:array[1..100] of muchie;
    l:array[1..100] of integer;
f:text;
i,j,k,p,m,n,z:integer;
ct:real;

function divide(p,q:indice):indice;
var st,dr:indice; 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:indice);
var m:indice;
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);

readln(f,n,m);
  for i:=1 to m do readln(f,v[i].x,v[i].y,v[i].cost);


qsort(1,m);
z:=0;
for i:=1 to n 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(z);w[z]:=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:0:0);
writeln(g,z);
for i:=1 to z do writeln(g,w[i].x,' ',w[i].y);
close(f);
close(g);
end.