Program hamolton;
 type lista=^celula;
      celula=record
        nod:longint;
        next:lista;
        end;
const inf=1000000000;
var a:array [0..18] of lista;
    v:lista;
    c:array [0..1 shl 18,0..18] of longint;
    i,j,n,m,x,y,co,rez:longint;
    cost:array [0..18,0..18] of longint;
    fi,fo:text;
function min(x,y:longint):longint;
begin
 if x<y then min:=x else min:=y;
end;
begin
 assign(fi,'hamilton.in');
  assign(fo,'hamilton.out');
 reset(fi); rewrite(fo); readln(fi,n,m);
 {    _____________________    }
  for i:=1 to n do
   for j:=1 to n do cost[i,j]:=inf;
  for i:=1 to m do begin
                    readln(fi,x,y,co);
                    cost[x,y]:=co;
                    new(v); v^.nod:=x; v^.next:=a[y]; a[y]:=v;
                    end;
  {   _____________________   }
  for i:=0 to 1 shl n do
   for j:=0 to n do c[i,j]:=inf;
  c[1,0]:=0;
  {   ______________________  }
   for i:=0 to (1 shl n)-1 do
    for j:=0 to n-1 do
     if i and (1 shl j)<>0 then begin
      v:=a[j];
       while v<>nil do begin
        if i and (1 shl v^.nod)<>0 then c[i,j]:=min(c[i,j],c[i xor (1 shl j)][v^.nod]+cost[v^.nod][j]);
         v:=v^.next;
        end;
     end;
   { _______________________  }
   rez:=inf;
     v:=a[0];
       while v<>nil do begin
        if i and (1 shl v^.nod)<>0 then rez:=min(rez,c[1 shl n-1][v^.nod]+cost[v^.nod][0]);
         v:=v^.next;
        end;
   if rez=inf then write(fo,'Nu exista solutie')
    else write(fo,rez);
  close(fo);
end.