#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 20;
const int MAXX = 262150; // ( 1 << 18 ) , 262144
const int INF = 100000000;
int M , N, sol;
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];
vector<int> G[MAXN];
int main()
{   ifstream f("hamilton.in");  
	ofstream g("hamilton.out");
	f>>N>>M;
	for(int i=0; i<N; ++i) 
		for(int j=0; j<N; ++j) 
			Cost[i][j] = INF;
	for(;M;M--){
		int x , y; 
		f>>x>>y;
		G[y].push_back(x); // greseala dvs ( inversare )
		f>>Cost[x][y]; // greseala dvs ( inversare )
	}
	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(size_t k=0;k < G[j].size();++k)
					if(i & (1<<G[j][k]))
						C[i][j] = min(C[i][j],C[i ^ (1<<j)][G[j][k]] + Cost[G[j][k]][j]);
	sol = INF;
	for(size_t i=0; i<G[0].size(); ++i)
		sol = min(sol,C[(1<<N) - 1][G[0][i]] + Cost[G[0][i]][0]);
	if(sol==INF) g<<"Nu exista solutie"<<'\n';
	else g<<sol<<'\n';
	return 0;
}