#include <fstream>
#include <vector>
#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],cost[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].push_back(c);
  }
}

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

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

}

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

  for (int i = 0; i < v[0].size(); ++i) {
      solutie = min(solutie, c[v[0][i]][(1<<n)-1] + cost[0][i]);
    }
  if (solutie == INF) {
    out<<"Nu exista solutie\n";
  } else {
    out<<solutie<<"\n";
  }
}

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