#include <fstream>
#include <vector>

using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
const int NMAX=20,INF=1e9;
int n,m,cost[NMAX][NMAX],dp[NMAX][(1<<NMAX)],rez,x,y,c;
vector <int> V[NMAX];
int main()
{
	fi>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fi>>x>>y;
		fi>>cost[y][x];
		V[y].push_back(x);
	}
	for(int i=0;i<n;i++)
		for(int conf=0;conf<(1<<n);conf++)
			dp[i][conf]=INF;
	dp[0][1]=0;
	for(int conf=1;conf<(1<<n);conf++)
		for(int i=0;i<n;i++)
			if((1<<i)&conf)
				for(auto x:V[i])
					if(conf&(1<<x))
						dp[i][conf]=min(dp[i][conf],dp[x][conf^(1<<i)]+cost[i][x]);
	rez=INF;
	for(auto i:V[0])
		if(dp[i][(1<<n)-1]!=INF)
			rez=min(rez,dp[i][(1<<n)-1]+cost[0][i]);
	if(rez==INF)
		fo<<"Nu exista solutie";
	else fo<<rez<<"\n";
	fi.close();
	fo.close();
	return 0;
}