#include <fstream>
#include <limits>
#include <vector>
#include <list>
#include <algorithm>

const unsigned INF=std::numeric_limits<unsigned>::max()/2;


int main(){
	std::ifstream fin("hamilton.in");
	std::ofstream fout("hamilton.out");

	unsigned n,m; fin>>n>>m;

	std::vector< std::list <unsigned> > in(n);
	std::vector< std::vector<unsigned> > Cost(n,std::vector<unsigned>(n,INF));

	for(unsigned i=0;i<m;++i){
		unsigned x,y,c; fin>>x>>y>>c;
		Cost[x][y]=c;
		in[y].push_back(x);
	}

	std::vector< std::vector<unsigned> > C(1<<n,std::vector<unsigned>(n,INF));
	C[1][0]=0;


	for(unsigned i=1; i<(1u<<n); ++i)
		for(unsigned j=0; j<n; ++j)
			if(i&(1<<j))
				for(auto it=in[j].begin();it!=in[j].end();++it)
					if(i&(1<<*it))
						C[i][j]=std::min(C[i][j], C[i^(1<<j)][*it]+Cost[*it][j] );


	unsigned sol=INF;

	for(auto it=in[0].begin();it!=in[0].end();++it)
		sol=std::min(sol, C[(1<<n)-1][*it] + Cost[*it][0] );

	if(sol==INF) fout<<"Nu exista solutie\n";
	else fout<<sol<<'\n';
}