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

using namespace std;

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

int d[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 < M; ++i) {
      int x, y, w;
      scanf("%d %d %d", &x, &y, &w);
      C[x][y] = w;
   }


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

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

   d[1][0] = 0;

   for (int k = 1; 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[k ^ (1 << j)][v];

               if ((k & (1 << v)) && prev < inf) {
                  d[k][j] = min(d[k][j], d[k ^ (1 << j)][v] + C[v][j]);
               }
            }

         }
      }
   }

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

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

   fclose(stdin);
   fclose(stdout);
}