#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int NMAX = 19;
const int LMAX = (1 << 18);
const int INF = 0x3f3f3f3f;

struct edge {
  int to, cost;
};

int n, m, DP[LMAX][NMAX];
vector<edge> G[NMAX];

void read() {
  scanf("%d%d", &n, &m);
  int x, y, cost;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &cost);
    G[x + 1].push_back({y + 1, cost});
  }
}

inline int bit(int x) {
  return 1 << (x - 1);
}

inline int has_bit(int mask, int x) {
  return mask & bit(x);
}

void solve() {
  memset(DP, INF, sizeof(DP));
  
  DP[1][1] = 0;
  for (int mask = 1; mask < (1 << n); mask++)
    for (int last = 1; last <= n; last++)
      if (has_bit(mask, last)) {
        for (auto& edg: G[last]) {
          if (!has_bit(mask, edg.to)) {
            DP[mask ^ bit(edg.to)][edg.to] = min(
              DP[mask ^ bit(edg.to)][edg.to],
              DP[mask][last] + edg.cost);
          }
        }
      }

  int fbits = bit(n + 1) - 1, res = INF;
  for (int last = 1; last <= n; last++)
    for (auto& edg: G[last]) {
      if (edg.to == 1) {
        res = min(res, DP[fbits][last] + edg.cost);
      }
    }

  if (res == INF) {
    printf("Nu exista solutie\n");
  } else {
    printf("%d\n", res);
  }
}

int main() {
  freopen("hamilton.in", "r", stdin);
  freopen("hamilton.out", "w", stdout);

  read();
  solve();

  return 0;
}