program aaaa;
type mi=record
     x,y,c:longint;
     end;
var f,g:text;
    n,m,i,j,c,k,min:longint;
    ok:boolean;
    aux:mi;
    s:array[1..200005] of longint;
    a:array[1..200000,1..200000] of integer;
    v:array[1..200000] of mi;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
  readln(f,n,m);
    for i:=1 to m do
      begin
         readln(f,v[i].x,v[i].y,v[i].c);
      end;
      k:=0;
    for i:=1 to n do
      s[i]:=1;
    for k:=1 to n-1 do
      begin
        min:=maxlongint;
        for i:=1 to n do
           if (s[i]<>0) and (min>a[s[i],i]) then
             begin
              min:=a[s[i],i];
              j:=i;
             end;
        c:=c+min;
        v[k].x:=s[j];
        v[k].y:=j;
        for i:=1 to n do
           if (s[i]=1) and (a[i,s[i]]>a[i,j]) then
              s[i]:=j;
        s[j]:=0;
      end;
    writeln(g,c);
    writeln(g,n-1);
    for i:=1 to k do
      writeln(g,v[i].x,' ',v[i].y);
close(f);
close(g);
end.