#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 18
#define MAXVAL 1000000001

using namespace std;

vector<vector<int>> v, cost;
int d[MAXN][2 << MAXN], cicle[MAXN];

int noNodes, n, firstNode;

int main(){
  int i, a, b, c, m, mask, x, j;

  ifstream fin("hamilton.in");
  fin >> n >> m;
  v.resize(n);
  cost.resize(n);

  for(i = 0; i < m; i ++){
    fin >> a >> b >> c;

    v[a].push_back(b);
    cost[a].push_back(c);

    // Avem muchie pana la nodul de start
    if(b == 0)
      cicle[a] = c;
  }
  fin.close();

  noNodes = 0;
  firstNode = 0;

  for(mask = 0; mask < (1 << n); mask ++)
    for(i = 0; i < n; i ++)
      d[i][mask] = MAXVAL;
  d[0][1 << 0] = 0; // Traseul de la 0 la 0 are costul 0

  for(mask = 0; mask < (1 << n); mask ++){
    for(i = 0; i < n; i ++){
      // Daca nodul I exista in masca mask
      if(mask & (1<<i)){

        // Exista muchie i -- v[i][j]
        for(j = 0; j < v[i].size(); j ++){
          int other = v[i][j];
          int val = d[i][mask] + cost[i][j];
          // printf("d[ %d ][ %d ] -> d[ %d ][ %d ]\n", i, mask, v[i][j], mask | (1 << v[i][j]));

          if(!(mask & (1 << other)) && val < d[other][mask | (1 << other)])
            d[other][mask | (1 << other)] = val;
        }
      }
    }
  }

   // for(mask = 0; mask < (1 << n); mask ++)
   //  for(i = 0; i < n; i ++){
   //    printf("d[ %d ][ %d ] =  %d\n", i, mask, d[i][mask]);
   //  }

  x = MAXVAL;
  for(i = 0; i < n; i ++){
    if(cicle[i] != 0 && cicle[i] + d[i][(1 << n) - 1] < x)
      x = cicle[i] + d[i][(1 << n) - 1];
  }

  ofstream fout("hamilton.out");
  if(x == MAXVAL)
    fout << "Nu exista solutie" << endl;
  else
    fout << x << endl;
  fout.close();
  return 0;
}