type muchie=^nod;
     nod = record n,c:longint; a:muchie; end;

var v:array[1..200000] of muchie;
    arb:array[0..400000] of record x, y:longint; c:integer; end;
    aux:record x, y:longint; c:integer; end;
    viz:array[1..200000] of boolean;
    fin:array[1..2, 1..200000] of longint;
    buf:array[1..1 shl 17] of char;
    cost:int64;
    m, n, i, x, y, c, an, tot:longint;
    p, r:muchie;
    ok:boolean;
    f, g:text;

procedure inheap (a:longint);
  begin
  if a<> 1 then
    begin
    while (arb[a].c<arb[a div 2].c) and (a<>1) do
      begin
      aux.x:=arb[a].x; arb[a].x:=arb[a div 2].x; arb[a div 2].x:= aux.x;
      aux.y:=arb[a].y; arb[a].y:=arb[a div 2].y; arb[a div 2].y:= aux.y;
      aux.c:=arb[a].c; arb[a].c:=arb[a div 2].c; arb[a div 2].c:= aux.c;
      a:=a div 2;
      end;
    end;
  end;

procedure exheap (a:longint);
var b:longint;
  begin
  b:=1;
  while b<>0 do
    begin
    b:=0;
    if a*2<=an then
      begin
      b := a*2;
      if (a*2+1<=an) and (arb[a*2+1].c<arb[a*2].c) then b:=a*2+1;
      end;
    if arb[a].c<arb[b].c then b:=0;
    if b<>0 then
      begin
      aux.x:=arb[a].x; arb[a].x:=arb[b].x; arb[b].x:=aux.x;
      aux.y:=arb[a].y; arb[a].y:=arb[b].y; arb[b].y:=aux.y;
      aux.c:=arb[a].c; arb[a].c:=arb[b].c; arb[b].c:=aux.c;
      a:=b;
      end;
    end;
  end;

begin
assign (f, 'apm.in'); settextbuf (f, buf); reset (f);
assign (g, 'apm.out'); settextbuf (g, buf); rewrite (g);

read (f, n, m);
for i := 1 to m do
  begin
  read (f, x, y, c);
  new(p); p^.n:=y; p^.c:=c; p^.a:=v[x]; v[x]:=p;
  new(p); p^.n:=x; p^.c:=c; p^.a:=v[y]; v[y]:=p;
  end;

x:=1; viz[1]:=true; tot:=0; an:=0; cost:=0;
while tot < n-1 do
  begin
  p:=v[x];                                    //p-nodul in care suntem
  while p <> nil do
    begin
    if viz[p^.n] = false then                 //punem in heap toate muchiile spre noduri nevizitate inca
      begin
      an:=an+1;
      arb[an].x:=x;arb[an].y:=p^.n; arb[an].c:=p^.c;
      inheap(an);
      end;
    p:=p^.a;                                   //parcurgem mai departe vecinii nodului p
    end;

  ok:= true;
  while ok do
    begin
    if viz[arb[1].y] = false then              //cautam in heap muchia de cost minim spre un nod nevizitat
      begin
      ok:= false;                              //ok=false - am gasit-o

      viz[arb[1].y]:=true;                     //marcam nodul ca si vizitat si salvam pentru afisarea finala
      tot:=tot+1;
      fin[1, tot]:=arb[1].x; fin [2, tot]:=arb[1].y;
      cost:=cost+arb[1].c;

      x:=arb[1].y;                              // din x vom cauta noi muchii data viitoare
      end;
                                                //eliminarea din heap
    arb[1]:=arb[an]; an:=an-1;
    exheap(1);
    end;
  end;

writeln (g, cost);
writeln (g, tot);
for i := 1 to tot do writeln (g, fin[1, i], ' ', fin [2, i]);

close (f); close (g);
end.