#include <cstdio>
#include <memory.h>
#include <vector>
#include <bitset>

using namespace std;

const int INF = 0x3f3f3f3f;
int N, M;
vector<vector<pair<int, int>>> Graph;
int DP[1<<18][18];
bitset<18> Computed[1<<18];

int hamilton(int mask, int k) {
  if (Computed[mask][k])
    return DP[mask][k];

  if (mask == 0)
    return INF;
  if (mask != 1 & k == 0)
    return INF;

  int crtBest = INF;
  for (auto v: Graph[k])
    if (mask & (1<<v.first)) 
      crtBest = min(crtBest, hamilton(mask ^ (1<<k), v.first) + v.second); 

  DP[mask][k] = crtBest;
  Computed[mask][k] = true;
  
  return DP[mask][k];
}

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

  scanf("%d%d", &N, &M);
  Graph.resize(N);
  int from, to, cost;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d%d", &from, &to, &cost);
    Graph[to].emplace_back(from, cost);
  }

  memset(DP, INF, sizeof(DP));
  Computed[1][0] = true;
  DP[1][0] = 0;

  int best = INF;
  int mask = (1 << N) - 1;

  for (auto v: Graph[0])
    best = min(best, hamilton(mask, v.first) + v.second);

  if (best >= INF)
    printf("Nu exista solutie\n");
  else
    printf("%d\n", best);
  return 0;
}