#include <fstream>
#include <vector>
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
#define INF 100000000

int j,i,x,y,n,m,c[1<<19][20],cost[20][20],sol=INF;
vector< int > a[20];

int main(){
	
	fi >> n >> m;
	
	for (i=0; i<n; i++) for (j=0; j<n; j++) cost[i][j]=INF;
	
	for (i=1; i<=m; i++){
		fi >> x >> y;
		a[y].push_back(x);
		fi >> cost[x][y];
	}

	for (i=0; i<1<<n; i++) for (j=0; j<n; j++) c[i][j]=INF;
	c[1][0]=0;
	
	for (i=0; i<1<<n; i++)
		for (j=0; j<n; j++)
			if (i & (1<<j)) 
				for (size_t 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]);
		
	for (size_t k=0; k<a[0].size(); k++)
		sol=min(sol,c[(1<<n)-1][a[0][k]]+cost[a[0][k]][0]);
	
	if (sol==INF) fo << "Nu exista solutie"; else fo << sol;			
					
	return 0;
}