program kruskal;

type much=record x,y,c:longint; end;

var fi,fo:Text;
    bufin,bufout:array[1..1 shl 17]of char;
    muchie:Array[1..400000]of much;
    sol:array[0..1,1..400000]of longint;
    n,m,nrmuchii,costtotal,k,i,j,cost:integer;
    t,h:array[1..200000]of longint;

  procedure citire;
  var i,x1,y1,c1:integer;
  begin
      readln(fi,n,m);
      for i:=1 to m do
        begin
            readln(fi,x1,y1,c1);
            with muchie[i] do
              begin
                  x:=x1;
                  y:=y1;
                  c:=c1;
              end;
        end;
  end;


    procedure swap(var a,b:much); var c:much; begin c:=a; a:=b; b:=c; end;

  procedure quick(s,d:longint);
  var a,b,ai:longint; aux:much;
  begin
      a:=s; b:=d;
      repeat
        while muchie[a].c<muchie[b].c do dec(b);
        swap(muchie[a],muchie[b]); inc(A); ai:=1;
        if a<b then
          begin
              while muchie[a].c<muchie[b].c do inc(A);
              if a<b then
                begin
                  swap(muchie[a], muchie[b]); dec(b); ai:=0;
                end;
          end;
      until b<=a;
      if s<a-ai then quick(s,a-ai);
      if a-ai+1<d then quick(a-ai+1,d);
  end;

  procedure init_multimi_disjuncte;
  var i:longint;
  begin
      for i:=1 to n do
        begin
            t[i]:=i;  //radacina arborelui e propriul parinte
            h[i]:=0;  //initial fiecare arbore va contine un singur nod
        end;
  end;

  function multime(nod:longint):longint;
  begin
      if nod<>t[nod] then
        t[nod]:=multime(t[nod]);
        multime:=t[nod];
  end;

  procedure reuneste(i,j:longint);
  begin
      i:=multime(i); j:=multime(j);
      if i<>j then
      begin
        if h[i]>h[j] then t[j]:=i else t[i]:=j;
        if h[i]=h[j] then h[j]:=h[j]+1;
      end;
  end;


begin
    assign(fi,'apm.in'); reset(fi); settextbuf(fi,bufin);
    assign(fo,'apm.out'); rewrite(fo); settextbuf(fo,bufout);

      citire;

      quick(1,m);

      init_multimi_disjuncte;

      nrmuchii:=0; //am adaugat 0 muchii in apm deocamdata

      costtotal:=0;
      for k:=1 to m do
        begin
            with muchie[k] do
              begin
                  i:=x; j:=y; cost:=c;
              end;
            if multime(i)<>multime(j) then //daca nodurile nu fac parte din
              begin                        //acelasi arbore, se "reunesc" multimile
                  reuneste(i,j);
                  writeln(cost);
                  costtotal:=costtotal+cost; //costul total al apmului
                  inc(nrmuchii); //am adaugat o muchie in apm
                  sol[0,nrmuchii]:=i;
                  sol[1,nrmuchii]:=j;
              end;
        end;

      writeln(fo,costtotal);
      writeln(fo,nrmuchii);
      for i:=1 to nrmuchii do
        writeln(fo,sol[0,i],' ',sol[1,i]);

    close(fi); close(fo);
end.