#include <cstdio>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

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

int hamilton(int mask, int k) {
  if (DP[mask][k] != INF)
    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)) 
      crtBest = min(crtBest, hamilton(mask ^ (1<<k), v) + Cost[v][k]); 

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

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

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

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

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

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

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