#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define Nmax 20
#define Mmax 1<<18+2
#define inf 0x3f3f3f3f

int N,M;
int Cost[Nmax][Nmax];
int C[Mmax][Nmax];
vector <int> l[Nmax];

int main()
{
    int a,b,c;
    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(int i=0;i<(1<<N);++i)
        for(int j=0;j<N;++j)
            C[i][j]=inf;

    for(int i=1;i<=M;++i)
        {
        scanf("%d%d%d",&a,&b,&c);
        l[b].push_back(a);
        Cost[a][b]=c;
        }

    C[1][0]=0;

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

    int Sol=inf;
    for(int i=0;i<(int)l[0].size();++i)
        Sol = min(Sol , C[(1<<N) - 1][ l[0][i] ] + Cost[ l[0][i] ][0]);

    if (Sol == inf)
        printf("Nu exista solutie\n");
    else
        printf("%d\n",Sol);

    return 0;
}