#include <stdio.h>
#define NMAX 18
#define LMAX (1<<18)
#define INF 1000000000
#define pb push_back
using namespace std;
int n,m,cost[NMAX][NMAX],best[NMAX][LMAX],rez;
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		cost[x][y]=z; 
	}
}
void init()
{
	int i,j;
	for (i=0; i<(1<<n); i++)
		for (j=0; j<n; j++)
			best[j][i]=INF;
	best[0][1]=0;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void solve()
{
	init();
	int i,j,k,state;
	for (i=0; i<(1<<n); i++)
		for (j=0; j<n; j++)
			if (i & (1<<j))
				for (k=0; k<n; k++)
					if (!(i & (1<<k)) && cost[j][k])
					{
						state=i ^ (1<<k);
						best[k][state]=min(best[k][state],best[j][i]+cost[j][k]);
					}
					
	rez=INF;
	for (i=0; i<n; i++)
		if (cost[i][0])
			rez=min(rez,best[i][(1<<n)-1]+cost[i][0]);
	
	if (rez==INF)
		printf("Nu exista solutie\n");
	else
		printf("%d\n",rez);
}
int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	read();
	solve();
	return 0;
}