#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <limits>

using namespace std;

const int NMAX = 19;
const int MMAX = 400;
const int WMAX = 1000005;
const int inf = numeric_limits<int>::max() - 1;
const long KMAX = 1 << (NMAX + 1);

int d[NMAX][KMAX][NMAX];

int C[NMAX][NMAX];

int N, M;


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

   scanf("%d %d", &N, &M);

   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
         C[i][j] = -1;
      }
   }

   for (int i = 0; i < N; ++i) {
      for (int k = 0; k < (1 << N); ++k) {
         for (int j = 0; j < N; ++j) {
            d[i][k][j] = inf;
         }
      }
   }

   for (int i = 0; i < N; ++i) {
      int k = 1 << i;
      d[i][k][i] = 0;
   }


   for (int i = 0; i < M; ++i) {
      int x, y, w;
      scanf("%d %d %d", &x, &y, &w);
      C[x][y] = w;
   }



   for (int i = 0; i < N; ++i) {
      for (int k = 0; k < (1 << N); ++k) {
         for (int j = 0; j < N; ++j) {
            for (int v = 0; v < N; ++v) {
               if (C[v][j] != -1) {
                  int prev = d[i][k ^ (1 << j)][v];
                  if ((k & (1 << v)) && prev < WMAX) {
                     d[i][k][j] = min(d[i][k][j],
                           d[i][k ^ (1 << j)][v] + C[v][j]);
                  }
               }
            }
         }
      }
   }

   int all_nodes = (1 << N) - 1;

   int sol = numeric_limits<int>::max();
   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
         if (C[j][i] != -1 && j != i && d[i][all_nodes][j] != inf) {
            sol = min(sol, d[i][all_nodes][j] + C[j][i]);
         }
      }
   }

   if (sol == inf) {
      printf("Nu exista solutie");
   } else {
      printf("%d", sol);
   }

   fclose(stdin);
   fclose(stdout);
}