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

const int INF = 1e9;
const int NMAX = 18;

std::vector<std::pair<int, int>> graph[1 + NMAX];

int dp[1 << NMAX][1 + NMAX];

int calc(int state, int last) {
  if (dp[state][last] != -1)
    return dp[state][last];

  dp[state][last] = INF;
  for (const auto& edge: graph[last]) {
    if (!(state & (1 << edge.first)))
      continue;

    int newState = state ^ (1 << last);
    dp[state][last] = std::min(dp[state][last], calc(newState, edge.first) + edge.second);
  }

  return dp[state][last];
}

int main() {
  std::ifstream in("hamilton.in");
  std::ofstream out("hamilton.out");

  int n, m;
  in >> n >> m;

  if (n == 1) {
    out << "0\n";
    return 0;
  }

  for (int i = 1; i <= m; ++i) {
    int x, y, c;
    in >> x >> y >> c;

    graph[x].emplace_back(y, c);
  }

  for (int state = 0; state < (1 << n); ++state) {
    for (int last = 0; last < n; ++last)
      dp[state][last] = -1;
  }
  dp[1][0] = 0;

  int ans = INF;
  for (const auto& edge: graph[0]) {
    int c = calc((1 << n) - 1, edge.first) + edge.second;

    ans = std::min(ans, c);
  }

  if (ans == INF) {
    out << "Nu exista solutie\n";
    return 0;
  }

  out << ans << '\n';

  return 0;
}