#include <bits/stdc++.h>

using namespace std;

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

int cost[20][20],dp[1<<20][20];
vector<int> graf[20];
const int INF=1<<20;
int main()
{
	int n,m;
	in>>n>>m;
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			dp[i][j]=INF;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		in>>x>>y>>c;
		graf[y].push_back(x);
		cost[x][y]=c;
	}
	dp[1][0]=0;
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)
		{
			if(i&&(1<<j))
			{
				int nod=j;
				for(auto vecin:graf[nod])
					if(i&(1<<vecin))
						dp[i][nod]=min(dp[i][nod],dp[i-(1<<nod)][vecin]+cost[vecin][nod]);
			}
		}
	int ans=INF;
	for(auto vecin:graf[0])
		ans=min(ans,dp[(1<<n)-1][vecin]+cost[vecin][0]);
	if(ans==INF)
		out<<"Nu exista solutie"<<"\n";
	else
		out<<ans<<"\n";
	return 0;
}