uses crt;
type elem=record
     el:longint;
     ms:longint;
     su:longint;
     end;
     vek=array[1..400000] of elem;
     vi=array[1..400000 ] of longint;
var v:vek;
    w,t:vi;
    o:elem;
    n,k,m,a,i,j,b,c:integer;
   f,g:text;
begin
clrscr;
assign(f,'apm.in');
reset(f);
readln(f,n,m);
assign(g,'apm.out');
rewrite(g);
for i:= 1 to m do
begin
 readln(f,a,b,c);
 v[i].el:=a;
 v[i].ms:=b;
 v[i].su:=c;
end;
j:=1;
while j<>m do
begin
k:=j;
for i:= j to m do
  if (v[k].su) > (v[i].su) then
                             begin
                             k:=i;
                             end;
 o:=v[k];
 v[k]:=v[j];
 v[j]:=o;
 inc(j);
end;
for i:= 1 to n do
t[i]:=i;
w[1]:=2;
for i:= 1 to m do
begin
 if (t[v[i].ms]<>t[v[i].el]) and ((t[v[i].el])<>(t[v[i].ms])) then
 begin
   w[w[1]]:=i;
  inc(w[1]);
  b:=t[v[i].el];
  c:=t[v[i].ms];
  for j:= 1 to n do
  if t[j]=b  then t[j]:=c;

 end;
end;
a:=0;
for i:= 2 to w[1]-1 do
  a:=a+v[w[i]].su;
writeln(g,a);
writeln(g,n-1);
for i:= 2 to w[1]-1 do
 writeln(g,v[w[i]].el,v[w[i]].ms);

close(g);
close(f);
end.