#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

const int N = 20;
const int M = 262150;
const int inf = 100000000;

int n, m;
vector<int> vecini[N];
int cost[N][N];
int dp[M][N];

void citire()
{
	scanf("%d %d", &n, &m);

	int tmp1, tmp2, tmp3;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cost[i][j] = 0;
		}
	}

	for(int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

		vecini[tmp2].push_back(tmp1);
		cost[tmp1][tmp2] = tmp3;
	}

	for(int i = 0; i < (1 << n); i++)	
	{
		for(int j = 0; j < n; j++)	
		{
			dp[i][j] = inf;
		}
	}
}

void solve()
{
	dp[1][0] = 0;

	for(int i = 0; i < (1 << n); i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i & (1 << j))
			{
				int l = vecini[j].size();

				for(int k = 0; k < l; k++)
				{
					if(i & (1 << vecini[j][k]))
					{
						dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][vecini[j][k]] + cost[vecini[j][k]][j]);
					}
				}
			}
		}
	}

	int sol = inf;
	int l = vecini[0].size();

	for(int i = 0; i < l; i++)
	{
		sol = min(sol, dp[(1 << n) - 1][vecini[0][i]] + cost[vecini[0][i]][0]);
	}

	if(sol == inf)
	{
		printf("Nu exista solutie\n");
	}
	else
	{
		printf("%d\n", sol);
	}
}

int main()
{
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	
	citire();
	solve();

	return 0;
}