#include <bits/stdc++.h>
using namespace std;
string __fname = "hamilton"; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out

const int maxn = 18;
const int maxm = 300;

int c[maxn][maxn];
vector <int> v[maxn];
int dp[1 << maxn][maxn];


int main() {
  int n,m;
  cin >> n >> m;
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      c[i][j] = 1e8;
    }
  }
  for (int i = 0; i < (1 << n); i++){
    for (int j = 0; j < n; j++){
      dp[i][j] = 1e8;
    }
  }
  for (int i = 0; i < m; i++){
    int x,y,z;
    cin >> x >> y >> z;
    c[x][y] = z;
    v[y].push_back(x);
  }
  dp[1][0] = 0;
  for (int i = 1; i < (1 << n); i++){
    for (int j = 1; j < n; j++){ // starea [i][j]
      if (i & (1 << j)) {
        for (int k: v[j]) { // k->j starea [i ^ (1 << j)][k] -> [i][j]
          dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + c[k][j]);
        }
      }
    }
  }
  int rs = 1e8;
  for (int i = 1; i < n; i++){
    rs = min(rs, dp[(1 << n) - 1][i] + c[i][0]);
  }

  if (rs == 1e8) {
    cout << "Nu exista solutie";
  }
  else {
    cout << rs;
  }

}