// infoarena: problema/hamilton //
#include <fstream>
using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int MAXN = 20;
const int MAXM = 400;

int c[MAXN][MAXN],i,j,n,m,d[1<<MAXN][MAXN],x,y,z,k;

int main()
{
	in>>n>>m;
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			c[i][j] = 1<<29;

	for(i=1; i<=m; i++)
	{
		in>>x>>y>>z;
		c[x][y] = z;
	}
	
	for(i=0; i<(1<<n); i++)
		for(j=0; j<n; j++)
			d[i][j] = 1<<29;
	d[1][0] = 0;
	for(i=3; i<(1<<n); i++)
		for(j=0; j<n; j++)
			if(i & (1<<j))
				for(k=0; k<n; k++)
					if(k!=j && c[k][j]!=(1<<29) && (i & (1<<k)))
						d[i][j] = min(d[i][j], d[i - (1<<j)][k] + c[k][j]);
	k = 1<<29;
	for(j=1; j<n; j++)
		if(c[j][0]!=(1<<29))
			k = min(k, d[(1<<n)-1][j]+c[j][0]);
	if(k >= 1<<29)
		out<<"Nu exista solutie";
	else
		out<<k;
	
	return 0;
}