#include <stdio.h>
#define MAXN 18
#define MAXM 306
#define INF 1000000000
int d[1 << MAXN][MAXN];
int nod[MAXM], next[MAXM], ult[MAXN], mat[MAXN][MAXN];

inline int min2(int a, int b){
  return a < b ? a : b;
}

int rezolv(int bin, int x, int n){
  if(d[bin][x] == -1){
    d[bin][x] = INF;
    int i = ult[x];
    while(i != -1){
      if(!(nod[i] == 0 && bin != (1 << x) + 1)){
        if(bin & (1 << nod[i])){
          d[bin][x] = min2(d[bin][x], rezolv(bin ^ (1 << x), nod[i], n) + mat[nod[i]][x]);
        }
      }
      i = next[i];
    }
  }
  return d[bin][x];
}

int main(){
  FILE *in = fopen("hamilton.in", "r");
  int n, m, i, j, x, y, c, dr = 0;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    ult[i] = -1;
    for(j = 0; j < n; j++)
      mat[i][j] = INF;
  }
  for(i = 0; i < (1 << n); i++)
    for(j = 0; j < n; j++)
      d[i][j] = -1;
  for(i = 0; i < n; i++)
    d[1 << i][i] = 0;
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &x, &y, &c);
    nod[dr] = x;
    next[dr] = ult[y];
    ult[y] = dr;
    dr++;
    mat[x][y] = c;
  }
  fclose(in);
  int rez = INF;
  for(i = ult[0]; i != -1; i = next[i]){
    rez = min2(rez, rezolv((1 << n) - 1, nod[i], n) + mat[nod[i]][0]);
  }
  FILE *out = fopen("hamilton.out", "w");
  if(rez == INF)
    fprintf(out, "Nu exista solutie");
  else
    fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}