program kruskal;

  var bufin,bufout:array [1..100000] of byte;
      n,m,i,k:longint;
      a:array [1..3,1..400000] of longint;
      pad:array [1..200000] of longint;{padure de multimi disjuncte}
      arbpart:array [1..2,1..200000] of longint;
      cost:int64;

procedure sort(l,r: longint);
      var                        {quicksort}
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[3,(l+r) div 2];
         repeat
           while a[3,i]<x do
            inc(i);
           while x<a[3,j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[1,i];
                a[1,i]:=a[1,j];
                a[1,j]:=y;
                y:=a[2,i];
                a[2,i]:=a[2,j];
                a[2,j]:=y;
                y:=a[3,i];
                a[3,i]:=a[3,j];
                a[3,j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

function parent(x:longint):longint;         {returneaza reprezentantul }
  var y:longint;                    {componentei conexe}
  begin
    if x=pad[x] then parent:=x else
      begin
        y:=parent(pad[x]);
        parent:=y;
        pad[x]:=y;
      end;
  end;

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

  readln(n,m);
  for i:=1 to m do readln(a[1,i],a[2,i],a[3,i]);
  sort(1,m);                        {sortarea muchiilor dupa cost}


  for i:= 1 to n do pad[i]:=i;

  for i:=1 to m do
    begin
      if parent(a[1,i])<>parent(a[2,i]) then
        begin
          cost:=cost+a[3,i];
          pad[parent(a[1,i])]:=pad[parent(a[2,i])];     {constructia arborelui partial de}
          inc(k);                          {cost minim}
          arbpart[1,k]:=a[1,i];
          arbpart[2,k]:=a[2,i];
        end;
    end;

  writeln(cost);
  writeln(n-1);
  for i:= 1 to n-1 do
    begin
      writeln(arbpart[1,i],' ',arbpart[2,i]);
    end;
  close(output);
end.