#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 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 mask = 0; mask < (1 << n); ++mask) {
    for (int last = 0; last < n; ++last)
      dp[mask][last] = INF;
  }
  dp[1][0] = 0;

  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int last = 0; last < n; ++last) {
      if (!(mask & (1 << last)))
        continue;

      int newMask = mask ^ (1 << last);
      for (const auto& edge: graph[last]) {
        if (mask & (1 << edge.first))
          dp[mask][last] = std::min(dp[mask][last], dp[newMask][edge.first] + edge.second);
      }
    }
  }

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

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

  out << ans << '\n';

  return 0;
}