#include <fstream>
#include <vector>
#include <math.h>
#define INF 1<<30
#define NMAx 20
using namespace std;
vector <short> GT[NMAx];
int n,sol,Cost[NMAx][NMAx],A[NMAx][NMAx];

int calc(int config,int last) {
	if(!A[config][last]) {
		int fiu;
		A[config][last]=INF;
		for(fiu=0;fiu<GT[last].size();fiu++)
			if(config&(1<<GT[last][fiu]))
				if( GT[last][fiu]!=0 || config==((1<<last)+1) )
					A[config][last]=min(A[config][last],calc(config^(1<<last),GT[last][fiu])+Cost[GT[last][fiu]][last]);
		}
	return A[config][last];
}
void citire() {
	int i,x,y,m,c;
	ifstream in("hamilton.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		GT[y].push_back(x);
		Cost[x][y]=c;
		}
	in.close();
}
void afis() {
	ofstream out("hamilton.out");
	if(sol==INF)
		out<<"Nu exista solutie\n";
	else
		out<<(sol-1)<<'\n';
	out.close();
}
int main() {
	
	citire();
	
	sol=INF;
	A[1][0]=1;
	for(int i=0;i<GT[0].size();i++)
		sol=min(sol,calc((1<<n)-1,GT[0][i])+Cost[GT[0][i]][0]);
	
	afis();
	
	return 0;
}