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

using namespace std;

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

inline int min(int x,int y){
  if(x<y)return x;
  return y;
}

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

  scanf("%d %d ",&N,&M);
  int x,y,z,conf;

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

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

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

  C[1][0] = 0;

  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;
}