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

const int MAXN = 20, MAXX = 1<<18 , INF = int(2e9);

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

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&N, &M);
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j)
            Cost[i][j] = INF;

    for(;M;M--)
    {
        int x , y;
        scanf("%d %d", &x, &y);
        G[y].push_back(x);
        scanf("%d", &Cost[x][y]);
    }
    for(int i = 0;i < 1<<N ;++i)
        for(int j=0;j<N;++j)
            C[i][j] = INF;

    C[1][0] = 0;
    for(int i=0;i<1<<N;++i)
        for(int j=0;j<N;++j)
            if(i & (1<<j))
                for(size_t k=0;k<G[j].size();++k)
                    if(i & (1<<G[j][k]))
                        C[i][j] = min(C[i][j],C[i ^ (1<<j)][G[j][k]] + Cost[G[j][k]][j]);

    int sol = INF;
    for(size_t i=0;i<G[0].size();++i)
        sol = min(sol,C[(1<<N) - 1][G[0][i]] + Cost[G[0][i]][0]);
    if(sol==INF)
        printf("Nu exista solutie\n");
    else printf("%d\n",sol);
    return 0;
}