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

var n,m,suma,k:longint;
    v,v2:array[1..400001] of muchie;
    t,rang:array[1..200001] 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 merge(st,dr,m:longint);
  var j,i,k:longint;
  begin
    i:=st;
    j:=m+1;
    k:=st-1;
    while (i<=m) and (j<=dr) do begin
      k:=k+1;
      if v[i].cost<v[j].cost then begin
        v2[k]:=v[i];
        i:=i+1;
      end else begin
        v2[k]:=v[j];
        j:=j+1;
      end;
    end;

    if i<=m then for j:=i to m do begin
      k:=k+1;
      v2[k]:=v[j];
    end else for i:=j to dr do begin
      k:=k+1;
      v2[k]:=v[i];
    end;
    for i:=st to dr do v[i]:=v2[i];
  end;

procedure ordonare(st,dr:longint);
  var m:longint;
  begin
    if st<>dr then begin
      m:=(st+dr) div 2;
      ordonare(st,m);
      ordonare(m+1,dr);
      merge(st,dr,m);
    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 uneste(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;
      uneste(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(1,m);
  minim;
  afisare;
END.