program APM; {Kruskal}

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

var n,m,i,fahossz,sum:longint;
    x:array[1..400001] of elem;
    a,h:array[1..200001] of longint;
    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;

function halmaz(i:longint):longint;
begin
 if (h[i]=i) then halmaz:=i
 else begin
  h[i]:=halmaz(h[i]);
  halmaz:=h[i];
 end;
end;

procedure egyesites(i,j:longint);
begin
 h[halmaz(i)]:=halmaz(j);
end;

begin
assign(f,'apm.in');
reset(f);
readln(f,n,m);
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;
sum:=0;
for i:=1 to m do
 if halmaz(x[i].a)<>halmaz(x[i].b) then begin
  inc(fahossz);
  a[fahossz]:=i;
  sum:=sum+x[a[fahossz]].k;
  egyesites(x[i].a,x[i].b);
 end;

assign(f,'apm.out');
rewrite(f);
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.