#include <fstream>
#include <vector>
using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;

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

int n, m, sol;
int cost[MAXN][MAXN];
int C[MAXX][MAXN];
vector <int> a[MAXN];


int main()
{
	fin>>n>>m;
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j) cost[i][j]=INF;
	for (int i=1;i<=m;++i)
	{
		int x, y;
		fin>>x>>y;
		a[y].push_back(x);
		fin>>cost[x][y];
	}
	for (int i=0;i<(1<<n);++i)
		for (int j=0;j<n;++j) C[i][j]=INF;
	C[1][0]=0;
	for (int i=0;i<(1<<n);++i)
		for (int j=0;j<n;++j)
			if (i&(1<<j))
				for (int k=0;k<a[j].size();++k)
					if (i&(1<<a[j][k]))
						C[i][j]=min(C[i][j], C[i^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
	sol=INF;
	for (int i=0;i<a[0].size();++i)
		sol=min(sol,C[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);
	if (sol==INF) fout<<"Nu exista solutie"<<endl;
	else fout<<sol<< endl;
	return 0;
}