#include<cstdio>
#include<list>
#include<vector>
#include<bitset>
using namespace std;
void read(),solve();
vector<pair<int,int> > V[20];
list<pair<int,int> >C;
bitset<20> B,B1;
int n,m,a,b,c,DP[20][300000],k,doila,i,j;
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));
	}
}
void solve()
{
	C.push_back(make_pair(0,0));
	for(;!C.empty();)
	{
		list<pair<int,int> >::iterator q=C.begin();
		B1=q->first;
		a=q->second;
		for(vector<pair<int,int> >::iterator it=V[a].begin();it!=V[a].end();it++)
		{
			b=it->first;
			c=it->second;
			if(B1[b])continue;
			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");
}