#include <bits/stdc++.h>

const int BITS = 18;
const int MAX_N = (1 << BITS);
const int INF = 1 << 25;

int n, m;
int answer = INF;

std::vector <int> graph[BITS];

int dp[MAX_N][BITS];
int price[BITS][BITS];

int main() {
  int u, v, cost;
  freopen("hamilton.in", "r", stdin);
  freopen("hamilton.out", "w", stdout);
  std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      price[i][j] = INF;
    }
  }
  while (m --) {
    std::cin >> u >> v >> cost;
    graph[u].push_back(v);
    price[u][v] = cost;
  }
  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i) {
      dp[mask][i] = INF;
    }
  }
  dp[1][0] = 0;
  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i) {
      if ((mask & (1 << i)) > 0) {
        for (v : graph[i]) {
          if ((mask & (1 << v)) == 0) {
            dp[(mask | (1 << v))][v] = std::min(dp[(mask | (1 << v))][v], dp[mask][i] + price[i][v]);
          }
        }
      }
    }
  }
  for (v : graph[0]) {
    answer = std::min(answer, dp[(1 << n) - 1][v] + price[v][0]);
  }
  if (answer == INF) {
    std::cout << "Nu exista solutie";
    return 0;
  }
  std::cout << answer << "\n";
  return 0;
}