#include<cstdio>
#define N 15000000
int i,j,d,k,v,n,m,a,b,r,p,t,c[262145][19],w[19][19],u[19],o=-1;
char q[N];
inline int A()
{
  	int s=0;
  	for(o++;q[o]>='0'&&q[o]<='9';o++)
  		s=s*10+q[o]-'0';
  	return s;
}
int main()
{
    freopen("hamilton.in","r",stdin),freopen("hamilton.out","w",stdout),fread(q,1,N,stdin),n=A(),m=A();
    while(m--)
        a=A(),b=A(),d=A(),w[a][b]=d;
    for(j=0;j<(1<<n);j++)
	{
        for(i=0;i<n;i++)
            c[j][i]=(j!=(1<<i))?(1<<30):0;
        for(i=t=0,k=j;k;k>>=1,i++)
        	if(k&1)
            	u[t++]=i;
        for(r=0;r<t;r++)
        	if(u[r])
			{
            	for(v=1<<30,p=0;p<t;p++)
            		if(w[u[p]][u[r]]&&v>w[u[p]][u[r]]+c[j^(1<<u[r])][u[p]])
                		v=w[u[p]][u[r]]+c[j^(1<<u[r])][u[p]];
            	c[j][u[r]]=v;
        	}
    }
    for(v=1<<30,j=0;j<n;j++)
    	if(w[j][0]&&v>c[(1<<n)-1][j]+w[j][0])
        	v=c[(1<<n)-1][j]+w[j][0];
    v==1<<30?printf("Nu exista solutie"):printf("%d",v);
}