#include<cstdio>
#include<list>
#include<vector>
#include<bitset>
using namespace std;
void read(),solve();
list<pair<int,int> >C;
bitset<20> B,B1;
int n,m,a,b,c,DP[20][1<<18],k,doila,i,j,sol,M[20][20];
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d%d",&a,&b,&c);
		//V[a].push_back(make_pair(b,c));
		M[a][b]=c;
	}
}
void solve()
{
	C.push_back(make_pair(1,0));
	for(;!C.empty();)
	{
		list<pair<int,int> >::iterator q=C.begin();
		B1=q->first;
		a=q->second;
		for(b=1;b<n;b++)
		{
			if(!M[a][b])continue;
			if(B1[b])continue;
			c=M[a][b];
			B1[b]=1;
			k=B1.to_ulong();
			if(!DP[b][k])
			{
				DP[b][k]=DP[a][q->first]+c;
				C.push_back(make_pair(k,b));
				B1[b]=0;
				continue;
			}
			if(DP[b][k]>DP[a][q->first]+c)
				DP[b][k]=DP[a][q->first]+c;
			B1[b]=0;
		}
		C.pop_front();
	}
	doila=1<<n;--doila;
	//DP[0][doila]>0?printf("%d\n",DP[0][doila]):printf("Nu exista solutie\n");
	sol=20000000;
	for(i=1;i<n;i++)
		if(DP[i][doila]&&M[i][0]&&DP[i][doila]+M[i][0]<sol)sol=DP[i][doila]+M[i][0];
	sol!=20000000?printf("%d\n",sol):printf("Nu exista solutie\n");
}