type ref=^nod;
nod=record
    nr,c:longint;
    adr:ref;
    end;
var v:array[0..20] of ref;
rez:array[0..262146,0..20] of longint;
n,m,i,x,y,z,all,temp,min:longint;
f,g:text;
u:ref;
function cmin(noduri,last:longint):longint;
         var u:ref;
         ret,tmp:longint;
         begin
         if (noduri and 1)=0 then
            begin
            cmin:=153000005;
            exit;
            end;
         if last=0 then
            begin
            cmin:=0;
            exit;
            end;
         if rez[noduri,last]>0 then
            begin
            cmin:=rez[noduri,last];
            exit;
            end;
         ret:=153000005;
         u:=v[last];
         while u<>nil do
               begin
               if ((u^.nr>0) or (noduri-(1 shl last)=1)) and (((1 shl u^.nr) and noduri)>0) then
                  begin
                  tmp:=cmin(noduri-(1 shl last),u^.nr)+u^.c;
                  if tmp<ret then
                     ret:=tmp;
                  end;
               u:=u^.adr;
               end;
         cmin:=ret;
         rez[noduri,last]:=ret;
         end;
begin
assign(f,'hamilton.in');
assign(g,'hamilton.out');
reset(f);rewrite(g);
readln(f,n,m);
for i:=1 to m do
    begin
    readln(f,x,y,z);
    new(u);
    u^.nr:=x;
    u^.c:=z;
    u^.adr:=v[y];
    v[y]:=u;
    end;
all:=(1 shl n)-1;
u:=v[0];
min:=153000005;
while u<>nil do
      begin
      temp:=cmin(all,u^.nr)+u^.c;
      if temp<min then
         min:=temp;
      u:=u^.adr;
      end;
if min>=153000005 then
   writeln(g,'Nu exista solutie')
else
    writeln(g,min);
close(f);close(g);
end.