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

const int NMAX = 18, INF = 0x3f3f3f3f;

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

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

    scanf("%i %i", &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)
    {
        scanf("%i %i %i", &X, &Y, &C);
        G[Y].push_back(X);
        Cost[X][Y] = C;
    }

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

    Best[1][0] = 0;

    for(int Conf = 1; Conf < (1 << N); ++ Conf)
        for(int i = 0; i < N; ++ i)
            if(Conf & (1 << i))
                for(vector<int> :: iterator j = G[i].begin(); j != G[i].end(); ++ j)
                    if(Conf & (1 << *j))
                        Best[Conf][i] = min(Best[Conf][i], Best[Conf ^ (1 << i)][*j] + Cost[*j][i]);

    int Ans = INF;
    for(int i = 0; i < N; ++ i)
        if(Best[(1 << N) - 1][i] != INF && Cost[i][0] != -INF)
            Ans = min(Ans, Best[(1 << N) - 1][i] + Cost[i][0]);

    if(Ans == INF) printf("Nu exista solutie\n");
    else printf("%i\n", Ans);
}