#include<fstream>
using namespace std;
ifstream F("hamilton.in");
ofstream G("hamilton.out");
int i,j,k,n,m,p,t,c[262145][19],w[19][19],u[19];
int main()
{
	F>>n>>m;
	while(m--)
    	F>>i>>j>>k,w[i][j]=k;
	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(i=0;i<t;++i)
            if(u[i]) {
                for(k=1<<30,p=0;p<t;++p)
                    if(w[u[p]][u[i]]&&k>w[u[p]][u[i]]+c[j^(1<<u[i])][u[p]])
                        k=w[u[p]][u[i]]+c[j^(1<<u[i])][u[p]];
                c[j][u[i]]=k;
            }
	}
	for(k=1<<30,j=0;j<n;++j)
        if(w[j][0]&&k>c[(1<<n)-1][j]+w[j][0])
            k=c[(1<<n)-1][j]+w[j][0];
	(k==1<<30)?G<<"Nu exista solutie":G<<k;
    return 0;
}