#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 20
#define MMAX 262150
#define INF 0x3f3f3f

using namespace std;

int N, M, ct[NMAX][NMAX], cost[NMAX][MMAX], sol = INF;
vector <int> g[NMAX];
vector <int>::iterator it;

void read()
{
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            ct[i][j] = INF;
    for(int i=1; i<=M; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        g[y].push_back(x);
        scanf("%d", &ct[x][y]);
    }
}

void solve()
{
    int i, j, nod;
    for(i=0; i<N; ++i)
        for(j=0; j < (1<<N); ++j)
            cost[i][j] = INF;
    cost[0][1] = 0;
    for(j=0; j < (1<<N); ++j)
        for(i=0; i < N; ++i)
            if(j & (1<<i))
            {
                for(it = g[i].begin(); it != g[i].end(); ++it)
                    if(j & (1<<(*it)))
                    {
                        nod = *it;
                        cost[i][j] = min(cost[i][j], cost[nod][j ^ (1<<i)] + ct[nod][i]);
                    }

            }
    for(it = g[0].begin(); it != g[0].end(); ++it)
        sol = min(sol, cost[*it][(1<<N) - 1] + ct[*it][0]);
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    read();
    solve();
    if(sol == INF)
        printf("Nu exista solutie");
    else
        printf("%d", sol);
    return 0;
}