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

#define INF 0x3f3f3f3f

vector<int> G[18];
int C[1 << 18][18], Cost[18][18];
int result = INF, N, M, node1, node2, c;


int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    memset(Cost, -1, sizeof(Cost));
    scanf("%i %i", &N, &M);
    for(int i = 1; i <= M; i++)
    {
            scanf("%i %i %i", &node1, &node2, &c);
            Cost[node1][node2] = c;
            G[node2].push_back(node1);
    }
    for(int i = 0; i < (1 << N); i++)
            for(int j = 0; j < N; j++)
                    C[i][j] = INF;
    C[1][0] = 0;
    vector<int> :: iterator it;
    for(int i = 1; i < (1 << N); i++)
            for(int 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]);
    for(int i = 0; i < N; i++)
          if(C[(1 << N) - 1][i] != INF && Cost[i][0] != -1)
                  result = min(result, C[(1 << N) - 1][i] + Cost[i][0]);
    if(N == 0) result = 0;
    if(result == INF) printf("Nu exista solutie\n");
    else printf("%i\n", result);
    return 0;
}