// dp[i][j] = costul minim daca am ajuns in nodul i si am trecut prin toate
// nodurile din j j o sa fie o submultime de noduri
//
// dp[n][{1,2..,n}] -> solutie
//
// dp[0][{0}] = 0
// dp[1][{0,1}] = 9
// dp[4][{0,1,4}] = 12
//
//
// {0,1,4} = 10011
//
// dp[i][mask] = costul minim daca am ajuns in nodul i si am trecut prin toate
// nodurile din masca j (j este reprezentarea binara a starii nodurilor prin
// care am trecut)
//
// suntem in starea dp[i][mask]
// exista muchie de la j la i cu cost c
// dp[i][mask] = min(dp[j][mask - (2^i)] + c), pt orice j astfel incat sa existe
// muchie de la j la i

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int kMaxN = 18;
const int kInf = 1 << 29;

vector<pair<int, int>> v[kMaxN];
int dp[1 << kMaxN][kMaxN];

int main() {
  ifstream cin("hamilton.in");
  ofstream cout("hamilton.out");

  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    v[y].push_back({x, c});
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (1 << n); j++) {
      dp[j][i] = kInf;
    }
  }

  dp[1][0] = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 1; i < n; i++) {
      if ((1 << i) & mask) {
        for (auto p : v[i]) {
          int j = p.first;
          int c = p.second;
          dp[mask][i] = min(dp[mask][i], dp[mask - (1 << i)][j] + c);
        }
      }
    }
  }

  int ans = kInf;
  for (auto p : v[0]) {
    int j = p.first;
    int c = p.second;
    ans = min(ans, dp[(1 << n) - 1][j] + c);
  }

  if (ans == kInf)
    cout << "Nu exista solutie";
  else
    cout << ans;

  return 0;
}