var     a:array[1..3,1..400000] of longint;
        v:array[1..3,1..200000] of longint;
        b:array[1..200000] of longint;
        n,m,i,j,sum:longint;
        f1,f2:text;

procedure sw(var a,b:longint);
var t:longint;
begin
  t:=a;
  a:=b;
  b:=t;
end;

procedure qs(left,right:longint);
var i,j,r:longint;
begin
  i:=left;
  j:=right;
  r:=a[3,(i+j) div 2];
  while i<j do
    begin
      while a[3,i]<r do inc(i);
      while a[3,j]>r do dec(j);
      if i<=j then
        begin
          sw(a[1,i],a[1,j]);
          sw(a[2,i],a[2,j]);
          sw(a[3,i],a[3,j]);
          inc(i);
          dec(j);
        end;
    end;
  if i<right then qs(i,right);
  if j>left then qs(left,j);
end;

procedure schimba(x,y:longint);
var     i:longint;
begin
  for i:=1 to n do
    if b[i]=x then b[i]:=y;
end;

begin
  assign(f1,'apm.in');
  assign(f2,'apm.out');
  reset(f1);
  rewrite(f2);
  readln(f1,n,m);

  for i:=1 to m do
    readln(f1,a[1,i],a[2,i],a[3,i]);

    qs(1,m);

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

  j:=0;
  for i:=1 to m do
    if b[a[1,i]]<>b[a[2,i]] then
      begin
        schimba(b[a[1,i]],b[a[2,i]]);
        inc(j);
        v[1,j]:=a[1,i];
        v[2,j]:=a[2,i];
        v[3,j]:=a[3,i];
        if j=n-1 then break;
      end;

  sum:=0;
  for i:=1 to n-1 do
    sum:=sum+v[3,i];

  writeln(f2,sum);
  writeln(f2,n-1);
  for i:=1 to n-1 do begin
  for j:=1 to 2 do
    write(f2,v[j,i],' ');
    writeln(f2);
  end;
  close(f2);
end.