type muchie=record
       n1,n2:longint;
       cost:integer;
     end;

var n,m,suma,k:longint;
    v:array[1..400001] of muchie;
    t:array[1..200000] of longint;
    s:array[1..400000] of longint;
    f,g:text;

procedure citire;
  var i,j:longint;
  begin
    assign(f,'apm.in');
    reset(f);
    readln(f,n,m);

    for i:=1 to m do begin
      read(f,v[i].n1);
      read(f,v[i].n2);
      readln(f,v[i].cost);
    end;
  end;

procedure ordonare;
  var i,j:longint;
  begin
    for i:=1 to m-1 do
      for j:=i+1 to m do
        if v[i].cost>v[j].cost then begin
          v[m+1]:=v[i];
          v[i]:=v[j];
          v[j]:=v[m+1];
        end;
  end;

procedure minim;
  var i,j,nr,f,p:longint;
  begin
    nr:=1;
    j:=1;
    for i:=1 to n do t[i]:=i;
    while nr<n do begin
      while t[v[j].n1]=t[v[j].n2] do begin
        inc(j);
      end;
      p:=t[v[j].n1];
      for f:=1 to n do
        if t[f]=p then t[f]:=t[v[j].n2];
      suma:=suma+v[j].cost;
      inc(k);
      s[k]:=j;
      inc(nr);
    end;
  end;

procedure afisare;
  var i:longint;
  begin
    assign(g,'apm.out');
    rewrite(g);
    writeln(g,suma);
    writeln(g,n-1);
    for i:=1 to k do
      writeln(g,v[s[i]].n1,' ',v[s[i]].n2,' ');
    close(g);
  end;

BEGIN
  citire;
  ordonare;
  minim;
  afisare;
END.