program aaaa;
type mi=record
     x,y:longint;
     end;
var f,g:text;
    n,m,i,j,c,k,min,x1,x2,x3:longint;
    s:array[1..1005] of longint;
    a:array[1..1000,1..1000] of integer;
    v:array[1..1000] of mi;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
  readln(f,n,m);
  for i:=1 to n do
     for j:=1 to n do
        if i=j then a[i,j]:=0
          else
            begin
              a[i,j]:=maxint;
              a[j,i]:=maxint;
            end;
    for i:=1 to m do
      begin
         readln(f,x1,x2,x3);
         a[x1,x2]:=x3;
         a[x2,x1]:=x3;
      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.