// DP[i][j] = cost minim pentru a ajunge din 0 in j trecand prin toate nodurile din i

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 19;
const int CMAX = (1<<18)+5;
const int INF = 1<<30;
int N,M,X,Y,C,DP[CMAX][NMAX],i,j,k,Cost[NMAX][NMAX],SOL;
vector<int> G[NMAX],GT[NMAX];
vector<int>::iterator it;
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(;M;M--)
    {
        scanf("%d%d%d",&X,&Y,&C);
        G[X].push_back(Y);
        GT[Y].push_back(X);
        Cost[X][Y]=C;
    }
    for(i=1;i<(1<<N);i++)
        for(j=0;j<N;j++) DP[i][j]=INF;
    DP[1][0]=0;
    for(i=1;i<(1<<N);i++)
        for(j=0;j<N;j++)
            if(i&(1<<j))
                for(it=G[j].begin();it!=G[j].end();it++)
                    if((i&(1<<*it))==0)
                        DP[i+(1<<*it)][*it]=min(DP[i+(1<<*it)][*it],DP[i][j]+Cost[j][*it]);
    SOL=INF;
    for(it=GT[0].begin();it!=GT[0].end();it++) SOL=min(SOL,DP[(1<<N)-1][*it]+Cost[*it][0]);
    if(SOL==INF) printf("Nu exista solutie\n");
    else printf("%d\n",SOL);
    return 0;
}