#include <fstream>
#include <vector>

using namespace std;

const int N = 18;
const int INF = (1 << 29);

vector<pair<int, int>> nxt[N];
int dp[N][1 << N];

int main() {
  ifstream cin("hamilton.in");
  ofstream cout("hamilton.out");
  int n, m;
  cin >> n >> m;
  while (m--) {
    int x, y, c;
    cin >> x >> y >> c;
    nxt[x].emplace_back(y, c);
  }
  cin.close();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < (1 << n); ++j)
      dp[i][j] = INF;
  dp[0][1] = 0;
  for (int j = 0; j < (1 << n); ++j)
    for (int i = 0; i < n; ++i)
      for (auto to: nxt[i])
        dp[to.first][j ^ (1 << to.first)] = min(dp[to.first][j ^ (1 << to.first)], dp[i][j] + to.second);
  int ans = INF;
  for (int i = 1; i < n; ++i)
    for (auto to: nxt[i])
      if (to.first == 0) {
        ans = min(ans, dp[i][(1 << n) - 1] + to.second);
        break;
      }
  if (ans != INF)
    cout << ans << "\n";
  else
    cout << "Nu exista solutie\n";
  cout.close();
  return 0;
}