var x,y,z:array[1..400000] of integer;
    n,m,i,j,k,min,cost:longint;
    t:array[1..200000] of longint;
    b:array[1..200000] of boolean;
    bi,bo:array[1..10000] of integer;



procedure initiere;
Begin
  assign(input,'apm.in');
  settextbuf(input,bi);
  reset(input);
  readln(n,m);
  for i:=1 to m do
    readln(x[i],y[i],z[i]);
  close(input);
  for i:=1 to n do
    b[i]:=true;
End;
BEGIN
  initiere;
  cost:=0;
  b[1]:=false;
  for j:=1 to n-1 do
    begin
      min:=maxint;
      k:=1;
      for i:=1 to m do
        if ((not b[x[i]]) and b[y[i]]) or ((not b[y[i]]) and b[x[i]]) then
          if z[i]<min then
            begin
              k:=i;
              min:=z[i]
            end;
      if b[x[k]] then b[x[k]]:=false else b[y[k]]:=false;
      b[y[k]]:=false;
      cost:=cost+z[k];
      t[j]:=k;
    end;
  cost:=0;
  for i:=1 to n-1 do
    cost:=cost+z[t[i]];
  assign(output,'apm.out');
  settextbuf(output,bo);
  rewrite(output);
  writeln(cost);
  writeln(n-1);
  for i:=1 to n-1 do
  writeln(x[t[i]],' ',y[t[i]]);
  close(output);


END.