#include <bits/stdc++.h>

using namespace std;


const int INF = 1e9, MAXN = 20;


struct Edge {
  int vec;
  int cost;
};

vector <Edge> gr[MAXN + 1];

int dp[1 << MAXN][MAXN];

int main() {
  int n, m, i, j, sol;
  freopen ("hamilton.in", "r", stdin);
  freopen ("hamilton.out", "w", stdout);
  scanf ("%d%d", &n, &m);
  for (i = 0; i < (1 << n); i++)
    for (j = 0; j < n; j++)
      dp[i][j] = INF;
  while (m--) {
    int x, y, c;
    scanf ("%d%d%d", &x, &y, &c);
    gr[y].push_back ({x, c});
  }
  dp[1][0] = 0;
  for (i = 1; i < (1 << n); i++) for (j = 0; j < n; j++) if (i & (1 << j)) for (Edge u : gr[j]) if (i & (1 << u.vec))  dp[i][j] = min (dp[i][j], dp[i - (1 << j)][u.vec] + u.cost);
  sol = INF;
  for (Edge u : gr[0])
    sol = min (sol, dp[(1 << n) - 1][u.vec] + u.cost);
  if (sol == INF)
    {printf ("Nu exista solutie\n"); return 0;}
  printf ("%d\n", sol);
  return 0;
}