#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f


vector<int> G[18];
int C[1 << 18][18], Cost[18][18], X, Y, cost, N, M, sol;


int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int i, j;
    vector<int> :: iterator it;
    scanf("%i %i", &N, &M);
    memset(Cost, -1, sizeof(Cost));
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i %i", &X, &Y, &cost);
          Cost[X][Y] = cost;
          G[Y].push_back(X);
    }
    for(i = 0; i < (1 << N); i++)
          for(j = 0; j < N; j++)
                C[i][j] = INF;
    C[1][0] = 0;
    for(i = 1; i < (1 << N); i++)
          for(j = 0; j < N; j++)
                if(i & (1 << j))
                     for(it = G[j].begin(); it != G[j].end(); ++it)
                            if(i & (1 << *it))
                                 C[i][j] = min(C[i][j], C[i ^ (1 << j)][*it] + Cost[*it][j]);
    sol = INF;
    for(i = 0; i < N; i++)
          if(C[(1 << N) - 1][i] != INF && Cost[i][0] != -1)
                  sol = min(sol, C[(1 << N) - 1][i] + Cost[i][0]);
    if(N == 0) sol = 0;
    if(sol == INF) printf("Nu exista solutie\n");
    else printf("%i\n", sol);
    return 0;
}