#include <bits/stdc++.h>

#define N 18 
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m;
int C[N][N], dp[1 << N][N];
vector<int> graf[N];

void read() {
  f>>n>>m;
  int x, y;
  for(int i = 1;i <= m;++i) {
    f>>x>>y>>C[y][x];
    graf[y].push_back(x);
  }
}

int recur(int conf, int node) {
  if(dp[conf][node] == -1) {
    
    dp[conf][node] = oo;

    for(const auto& vecin : graf[node]) {
      if((1 << vecin) & conf) {
        if(vecin == 0 && 1 + (1 << node) != conf) {
          continue;
        }

        dp[conf][node] = min(dp[conf][node], recur(conf ^ (1 << node), vecin) + C[node][vecin]);
      }
    }
  }
  return dp[conf][node];
}

void solve() {
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  int result = oo;

  for(const auto& vecin : graf[0]) {
    result = min(result, recur((1 << n) - 1, vecin) + C[0][vecin]);
  }

  if(result < oo) {
    g<<result;
  } else {
     g<<"Nu exista solutie";
  }
}

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