#include<cstdio>
#include<vector>
using namespace std;
const int nmax = 20;
const int lmax = (1<<18)+5;
int n,m,x,y,z,c[nmax][nmax],dp[lmax][nmax],i,j,sol;
vector<int> v[nmax],g[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,&z);
	    v[x].push_back(y);
	    g[y].push_back(x);
	    c[x][y]=z;
	}
	for(i=1;i<(1<<n);i++)
        for(j=0;j<n;j++) dp[i][j]=1<<30;
	dp[1][0]=0;
	for(i=1;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if((1<<j)&i)
                for(vector<int>::iterator it=v[j].begin();it!=v[j].end();it++)
                    if(((1<<*it)&i)==0)
                        dp[i+(1<<*it)][*it]=min(dp[i+(1<<*it)][*it],dp[i][j]+c[j][*it]);
    sol=1<<30;
    for(vector<int>::iterator it=g[0].begin();it!=g[0].end();it++)
        sol=min(sol,dp[(1<<n)-1][*it]+c[*it][0]);
    if(sol==1<<30) printf("Nu exista solutie\n");
    else printf("%d\n",sol);
	return 0;
}