#include <cstdio>
#define maxx 1<<18
#include <vector>
#define inf 0x3f3f3f3f
#include <algorithm>


using namespace std;

int C[maxx][18],cost[18][18],N,M,S;
vector <int> G[18];

int main(){

  freopen("hamilton.in","r",stdin);
  freopen("hamilton.out","w",stdout);

  scanf("%d %d ",&N,&M);
  int x,y,conf,z;
  for(conf = 0;conf < (1<<N);++conf)
    for(x = 0;x < N;++x)C[conf][x] = inf;

  for(x = 0;x < N;++x)
    for(y = 0;y < N;++y)cost[x][y] = inf;

  while(M--){
    scanf("%d %d %d ",&x,&y,&z);
    cost[x][y] = z;
    G[y].push_back(x);
  }

  C[1][0] = 0;
  S = inf;

  for(conf = 0; conf < (1<<N);++conf)
    for(x = 0; x < N;++x)
      if(conf & (1 << x))
        for(y = 0;y < G[x].size();++y)
           if(conf & (1 << G[x][y]))
              C[conf][x] = min(C[conf][x],C[conf ^ (1 << x)][G[x][y]] + cost[G[x][y]][x]);

  for(x = 0;x < G[0].size();++x)
    S = min(S,C[(1<<N)-1][G[0][x]] + cost[G[0][x]][0]);

  if(S == inf)printf("Nu exista solutie\n");
  else printf("%d\n",S);

  return 0;
}