#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 19
#define LMAX (1<<18)+1
#define INF 2000000000
using namespace std;

int n,m;
int c[NMAX][LMAX];
vector <int> v[NMAX];
int cost[NMAX][NMAX];

ifstream in("hamilton.in");
ofstream out("hamilton.out");

void read() {
  int a,b,c;
  in>>n>>m;
  for (int i = 0; i < m; ++i) {
    in>>a>>b>>c;
    v[b].push_back(a);
    cost[b][a] = c;
  }
}

void init()
{
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < (1<<n); ++j)
      c[i][j] = INF;
}

void solve()
{
  int dim,nod;
  init();
  c[0][1] = 0;
  for (int j = 1; j < (1<<n); ++j)
    for (int i = 0; i < n; ++i)
      if (j & (1<<i)) {
        dim = v[i].size();
        for (int k = 0; k < dim; ++k) {
          nod = v[i][k];
          if (j & (1<<nod)) {
              c[i][j] = min(c[i][j], c[nod][j ^ (1<<i)] + cost[i][nod]);
          }
        }
      }
  int solutie = INF;
  int lant = (1<<n) - 1;
  dim = v[0].size();
  for (int i = 0; i < dim; ++i) {
      nod = v[0][i];
      solutie = min(solutie, c[nod][lant] + cost[0][nod]);
    }

  if (solutie == INF) {
    out<<"Nu exista solutie\n";
  } else {
    out<<solutie<<"\n";
  }
}

int main() {
  read();
  solve();
  return 0;
}