#include<cstdio>
#include<fstream>
#include<vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int N=19;
const int inf=0x3f3f3f3f;
int d[(1<<N)][N],n,m,cost[N][N];
vector<int> a[N];
inline int min(int a,int b)
{
	return a<b ? a:b;
}
int main()
{
	f>>n>>m;
	int i,j,k,x,y,ct;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>ct;
		a[y].push_back(x);
		cost[x][y]=ct;
	}
	for(i=0;i< (1<<n);++i)
		for(j=0;j<=n;++j)
			d[i][j]=inf;
	d[1][0]=0;
	for(i=1;i< (1<<n);++i)
		for(j=0;j<=n;++j)
			if((1<<j) & i)
			{
				for(k=0;k<a[j].size();++k)
					if(i&(1<<a[j][k]))
					d[i][j]=min(d[i][j],d[i ^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
			}
	int sol=inf;
	for(i=0;i<a[0].size();++i)
		sol=min(sol,d[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);
	if(sol==inf)
		g<<"Nu are solutie";
	else
		g<<sol;
}