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

var n,m,suma,k:longint;
    v:array[1..400001] of muchie;
    t,rang: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;

function rad(x:longint):longint;
  var y,z:longint;
  begin
    y:=x;
    while t[x]<>x do x:=t[x];
    while t[y]<>y do begin
     z:=t[y];
     t[y]:=x;
     y:=z;
    end;
    rad:=t[x];
  end;

procedure merge(x,y:longint);
  begin
    if rang[x]<rang[y] then t[x]:=y else t[y]:=x;
    if rang[x]=rang[y] then inc(rang[x]);
  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 rad(v[j].n1)=rad(v[j].n2) do begin
        inc(j);
      end;
      merge(rad(v[j].n2),rad(v[j].n1));
      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.