#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;

int N, M, Sol;
vector <int> A[MAXN];
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];

int calc(int start, int conf, int last)
{
if (C[conf][last] == -1)
{
  C[conf][last] = INF;

  for (size_t i = 0; i < A[last].size(); ++i)
    if (conf & (1<<A[last][i]))
    {
      if (A[last][i] == start && ((conf ^ (1<<last)) != (1<<start))) continue;

      C[conf][last] = min(C[conf][last], calc(start, conf ^ (1<<last), A[last][i]) + Cost[A[last][i]][last]);
    }
}

return C[conf][last];
}

int main()
{
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

cin >> N >> M;

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j) Cost[i][j] = INF;

for (int i = 1; i <= M; ++i)
{
  int x, y, c;

  cin >> x >> y >> c;

  A[y].push_back(x); // retin muchia invers
  Cost[x][y] = c;
}

  Sol = INF;
  int i=0;
  memset(C, -1, sizeof(C));

  C[1][0] = 0;

  for (size_t j = 0; j < A[i].size(); ++j)
    Sol = min(Sol, calc(i, (1<<N)-1, A[i][j]) + Cost[A[i][j]][i]);

if (Sol != INF) cout << Sol << endl;
else cout << "Nu exista solutie" << endl;

return 0;
}