#include <cstdio>

const int MAX_N = 18;
const int MAX_M = MAX_N * MAX_N;

int last[MAX_N], mc[1+MAX_M], next[1+MAX_M], cost[1+MAX_M];
int stari[MAX_N][1 << MAX_N], matr[1+MAX_N][1+MAX_N];
const int INF = 1000000000;

int min(int a, int b) {
  if(a < b)
    return a;
  return b;
}

int main() {
  int n, m, a, b, c;
  FILE *fin = fopen("hamilton.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    fscanf(fin, "%d%d%d", &a, &b, &c);
    mc[i] = b;
    next[i] = last[a];
    last[a] = i;
    cost[i] = c;
    matr[a][b] = c;
  }
  fclose(fin);

  for(int i = 0; i < n; ++i)
    for(int j = 1; j < 1 << n; ++j)
      stari[i][j] = INF;
  stari[0][1] = 0;
  for(int i = 1; i < 1 << n; ++i) {
    for(int nod = 0; nod < n; ++nod) {
      if(stari[nod][i] != INF) {
        int m = last[nod];
        while(m != 0) {
          if(!((1 << mc[m]) & i))
            stari[mc[m]][i ^ (1 << mc[m])] = min(stari[mc[m]][i ^ (1 << mc[m])], stari[nod][i] + cost[m]);
          m = next[m];
        }
      }
    }
  }

  int sol = INF;
  for(int i = 0; i < n; ++i)
    if(matr[i][0] > 0)
      sol = min(sol, stari[i][(1 << n) - 1] + matr[i][0]);

  FILE *fout = fopen("hamilton.out", "w");
  if(sol == INF)
    fprintf(fout, "Nu exista solutie");
  else
    fprintf(fout, "%d", sol);
  fclose(fout);
  return 0;
}