type ref=^nod;
nod=record
    nod:longint;
    cost:integer;
    adr:ref;
    end;
var v:array[1..200000] of ref;
d,heap,poz,t:array[1..200000] of longint;
s:array[1..200000] of byte;
u:ref;
n,m,i,a,b,c,x,sol:longint;
f,g:text;
procedure perc(p:longint);
          begin
          while (p>1) and (d[heap[p]]<d[heap[p shr 1]]) do
                begin
                b:=heap[p];
                heap[p]:=heap[p shr 1];
                heap[p shr 1]:=b;
                poz[heap[p]]:=p;
                poz[heap[p shr 1]]:=p shr 1;
                p:=p shr 1;
                end;
          end;
procedure sift(p:longint);
          begin
          while (p<=x shr 1) and ((d[heap[p]]>d[heap[p*2]]) or (d[heap[p]]>d[heap[p*2+1]])) do
                begin
                if d[heap[p*2]]<d[heap[p*2+1]] then
                   c:=p*2
                else
                    c:=p*2+1;
                b:=heap[p];
                heap[p]:=heap[c];
                heap[c]:=b;
                poz[heap[p]]:=p;
                poz[heap[c]]:=c;
                p:=c;
                end;
          end;
begin
assign(f,'apm.in');
assign(g,'apm.out');
reset(f);rewrite(g);
readln(f,n,m);
for i:=1 to m do
    begin
    readln(f,a,b,c);
    if v[a]=nil then
       begin
       new(v[a]);
       v[a]^.nod:=b;
       v[a]^.cost:=c;
       v[a]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.nod:=b;
        u^.cost:=c;
        u^.adr:=v[a];
        v[a]:=u;
        end;
    if v[b]=nil then
       begin
       new(v[b]);
       v[b]^.nod:=a;
       v[b]^.cost:=c;
       v[b]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.nod:=a;
        u^.cost:=c;
        u^.adr:=v[b];
        v[b]:=u;
        end;
    end;
for i:=2 to n do
    d[i]:=maxlongint;
inc(x);
heap[x]:=1;
d[1]:=0;
poz[1]:=1;
for i:=1 to n do
    begin
    a:=heap[1];
    heap[1]:=heap[x];
    poz[heap[1]]:=1;
    poz[a]:=0;
    dec(x);
    sift(1);
    s[a]:=1;
    u:=v[a];
    inc(sol,d[a]);
    if i<>n then
       while u<>nil do
          begin
          if s[u^.nod]=0 then
             if poz[u^.nod]=0 then
                begin
                inc(x);
                heap[x]:=u^.nod;
                d[u^.nod]:=u^.cost;
                poz[heap[x]]:=x;
                perc(x);
                t[u^.nod]:=a;
                end
             else
                 if u^.cost<d[u^.nod] then
                    begin
                    d[u^.nod]:=u^.cost;
                    perc(poz[u^.nod]);
                    t[u^.nod]:=a;
                    end;
          u:=u^.adr;
          end;
    end;
writeln(g,sol);
writeln(g,n-1);
for i:=2 to n do
    writeln(g,t[i],' ',i);
close(f);close(g);
end.