// 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];
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(k=0;k<G[j].size();k++)
                    if((i&(1<<G[j][k]))==0)
                        DP[i+(1<<G[j][k])][G[j][k]]=min(DP[i+(1<<G[j][k])][G[j][k]],DP[i][j]+Cost[j][G[j][k]]);
    for(SOL=INF,i=0;i<GT[0].size();i++) SOL=min(SOL,DP[(1<<N)-1][GT[0][i]]+Cost[GT[0][i]][0]);
    if(SOL==INF) printf("Nu exista solutie\n");
    else printf("%d\n",SOL);
    return 0;
}