program arborePartialDeCostMinim;
var i,j,m,n,x,y,e1,e2:integer;
a:array[1..20000,1..20000] of integer;
{c:array[1..20000] of longint;}
s:array[1..20000] of 0..1;
t,dx,dy:array[1..20000] of integer;
f,g:text;
su,cost_min:longint;
begin
assign(f,'apm.in');reset(f);
assign(g,'apm.out');rewrite(g);
readln(f,n,m);
for i:=1 to n do begin s[i]:=0;{c[i]:=0};t[i]:=0;end;
for i:=1 to n do for j:=1 to n do a[i,j]:=0;
for i:=1 to m do
        begin
        readln(f,x,y,cost_min);
        a[x,y]:=cost_min;
        a[y,x]:=cost_min;
        end;
s[1]:=1;
su:=0;
for x:=1 to n-1 do
        begin
        e1:=-1;
        e2:=-1;
        cost_min:=maxint;
        for i:=1 to n do
                for j:=1 to n do if (s[i]=1)and(s[j]=0) then if(a[i,j]<>0) then
                                                                if(a[i,j]<cost_min) then begin
                                                                                        cost_min:=a[i,j];
                                                                                        e1:=i;
                                                                                        e2:=j;
                                                                                        end;
         s[e2]:=1;
         t[e2]:=e1;
         {c[e2]a[e1,e2];}
         su:=su+a[e1,e2];
         end;
writeln(g,su);
writeln(g,n-1);
for i:=2 to n do writeln(g,t[i],' ',i);
close(f);close(g);
end.