#include <cstdio>
#include <vector>
using namespace std;

const int NMAX = 20;
const int INF = 0x3f3f3f3f;
const int MASK_SIZE = (1 << 18) + 2;

int n, m;
vector<int> g[NMAX];
int cost[NMAX][NMAX];
int dp[NMAX][MASK_SIZE];

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

void init() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cost[i][j] = INF;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < (1 << n); j++)
      dp[i][j] = INF;
  dp[0][1] = 0;
}

void solve(int drum) {
  for (int nod = 0; nod < n; nod++) {
    if ((drum & (1 << nod)) == 0) continue;
    for (int vecin : g[nod]) {
      if ((drum & (1 << vecin)) == 0) continue;
      dp[nod][drum] = min(dp[nod][drum], dp[vecin][drum ^ (1 << nod)] + cost[vecin][nod]);
    }
  }
}

void calcMin() {
  int minim = INF;

  for (int vecin : g[0]) {
    minim = min(minim, dp[vecin][(1 << n) - 1] + cost[vecin][0]);
  }

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

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

  read();
  init();

  for (int drum = 1; drum < (1 << n); drum++)
    solve(drum);

  calcMin();

  return 0;
}