type muchie=^nod;
     nod = record n, c:longint; a:muchie; end;

var v:array[0..18] of muchie;
    chk:array [0.. 18] of boolean;
    i, j, n, m, x, y, c, cost, min, t:longint;
    p:muchie;
    f, g:text;

procedure dfs (a:muchie; b:longint);
  begin
  chk[b]:=true;
  inc(t);
  while a <> nil do
    begin
    if chk[a^.n]=false then
      begin
      cost:=cost+a^.c;
      dfs(v[a^.n], a^.n);
      cost:=cost-a^.c; dec(t); chk[a^.n]:=false;
      end
                    else
      begin
      if (a^.n=1) and (t=n) then
        begin
        cost:=cost+a^.c;
        if cost< min then min := cost;
        cost:=cost-a^.c;
        end;
      end;
    a:=a^.a;
    end;
  end;

begin
assign (f, 'hamilton.in'); reset (f);
assign (g, 'hamilton.out'); rewrite (g);

readln (f, n, m);
for i := 1 to m do
  begin
  readln (f, x, y, c);
  if v[x]= nil then begin new(v[x]); v[x]^.a:=nil; v[x]^.n:=y; v[x]^.c:=c; end
               else begin new (p); p^.n:=y; p^.a:=v[x]; v[x]:=p; p^.c:=c; end;
  end;

cost:=0; min:=maxlongint; t:=0;
dfs(v[1], 1);

if min=maxlongint then writeln (g, 'Nu exista solutie')
                  else writeln (g, min);

close (f); close (g);
end.