#include <cstdio>
#include <vector>
#include<algorithm>
#define infile "hamilton.in"
#define outfile "hamilton.out"
#define INF 1<<30
#define n_max 20
#define pb push_back
#define FOR(g) \
    for(vector<int> :: iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;

vector < int > v[n_max];

int dp[1<<n_max][n_max];

int Cost[n_max][n_max];

int N, M, Best;


void init()
{
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
			Cost[i][j] = INF;
		
	for(int i=0; i < 1<<N; ++i)
		for(int j=0;j < N; ++j)
			dp[i][j] = INF;
}


void citeste()
{
	freopen(infile, "r", stdin);
	
	int x, y, z;
	
	scanf("%d %d", &N, &M);

	init();
	
	while(M--)
	{
		scanf("%d %d %d", &x, &y, &z);
		
		v[y].pb(x);
		Cost[x][y] = z;
	}
	
	fclose(stdin);
}




void rezolva()
{
	dp[1][0] = 0;
	
	for(int i=1;i < 1<<N; ++i)
		for(int j=0; j<N; ++j)
			if(i & (1<<j))
				FOR(v[j])
				    if(i&(1<<*it))
						dp[i][j] = min(dp[i][j], dp[i^(1<<j)][*it] + Cost[*it][j]);
				
	Best = INF;
	FOR(v[0])
	    Best = min(Best, dp[(1<<N)-1][*it] + Cost[*it][0]);
}


void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	if(Best != INF)
		printf("%d\n", Best);
	else
		printf("Nu exista solutie\n");
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();	

	return 0;
}