#include <stdio.h>
#include <vector>

const int MAX_N = 18;
const int INF = 2e9;

int cost[MAX_N][MAX_N];
int cost_min[1 << MAX_N][MAX_N];
std::vector<int> G[MAX_N];

int main() {

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

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < MAX_N; i++)
    for (int j = 0; j < MAX_N; j++)
      cost[i][j] = INF;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    cost[u][v] = c;
    G[u].push_back(v);
  }
  for (int i = 0; i < (1 << n); i++)
    for (int end = 0; end < n; end++)
      cost_min[i][end] = INF;
  cost_min[1][0] = 0;
  for (int subSet = 0; subSet < (1 << n); subSet++)
    for (int end = 0; end < n; end++)
      if ((subSet & (1 << end)) > 0)
        for (int next : G[end])
          if ((subSet & (1 << next)) == 0) {
            int nextSubSet = subSet | (1 << next);
            cost_min[nextSubSet][next] = std::min(cost_min[nextSubSet][next], cost_min[subSet][end] + cost[end][next]);
          }
  int answer = INF;
  for (int node = 1; node < n; node++)
    if (cost[node][0] < INF)
      answer = std::min(answer, cost_min[(1 << n) - 1][node] + cost[node][0]);
  if (answer >= INF)
    printf("Nu exista solutie\n");
  else
    printf("%d\n", answer);

  return 0;
}