#include<cstdio>
#include<vector>
#define INF (1<<30)
#define NMAX 20
#define LMAX (1<<18)+10
using namespace std;
int n,m,cost[NMAX][NMAX],v[LMAX][NMAX];
vector<int> G[NMAX];
void init()
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cost[i][j]=INF;
	for(i=0;i<(1<<n);i++)
		for(j=0;j<n;j++)
			v[i][j]=INF;
	v[1][0]=0;
}
void read()
{
	freopen("hamilton.in","r",stdin);
	scanf("%d %d",&n,&m);
	init();
	int x,y,z;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		G[y].push_back(x);
		cost[x][y]=z;
	}
}
void solve()
{
	int i,j,k,sol;
	for(i=0;i<(1<<n);i++)
		for(j=0;j<n;j++)
			if(i & (1<<j))
				for(k=0;k<G[j].size();k++)
					if(i & (1<<G[j][k]))
						v[i][j]=min(v[i][j],v[i^(1<<j)][G[j][k]]+cost[G[j][k]][j]);
	sol=INF;
	for(i=0;i<G[0].size();i++)
		sol=min(sol,v[(1<<n)-1][G[0][i]]+cost[G[0][i]][0]);
	freopen("hamilton.out","w",stdout);
	if(sol==INF)
		printf("Nu exista solutie\n");
	else
		printf("%d\n",sol);
}
int main()
{
	init();
	read();
	solve();
	return 0;
}