program Kruskal;

type elem = record
      a,b,k:longint;
     end;

var n,m,i,j,fahossz,sum:longint;
    x:array of elem;
    a,h:array of longint;
    t:elem;
    f:text;

procedure quick(bal,jobb:longint);
var i,j,kozep:longint;
    t:elem;
begin
i := bal;
j := jobb;
kozep := x[(i+j) div 2].k;
while i<=j do begin
 while x[i].k<kozep do i := i + 1;
 while x[j].k>kozep do j := j - 1;
 if i<=j then begin
  t:=x[i];
  x[i]:=x[j];
  x[j]:=t;
  i := i + 1;
  j := j - 1;
 end;
end;
if bal < j then quick(bal,j);
if i < jobb then quick(i,jobb);
end;

begin
assign(f,'apm.in');
reset(f);
readln(f,n,m);
SetLength(a,n+1);
SetLength(h,n+1);
SetLength(x,m+1);
for i:=1 to m do
 readln(f,x[i].a,x[i].b,x[i].k);
close(f);

quick(1,m);

for i:=1 to n do
 h[i]:=i;

fahossz := 0;
i:=1;
while (fahossz<n-1) do begin
 if h[x[i].a]<>h[x[i].b] then begin
  inc(fahossz);
  a[fahossz] := i;
  for j:=1 to n do
   if h[j] = h[x[i].b] then h[j] := h[x[i].a];
 end;
 inc(i);
end;

assign(f,'apm.out');
rewrite(f);
sum:=0;
for i:=1 to fahossz do
 sum:=sum+x[a[i]].k;
writeln(f,sum);
writeln(f,fahossz);
for i:=1 to fahossz do
 writeln(f,x[a[i]].a,' ',x[a[i]].b);
close(f);
end.