#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int w[19][19];
int a, b, c;
int dp[262150][19];
int minn = 1000000000;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		w[a][b] = c;
	}

	for (int i = 0; i < (1 << n); i++)
	{
		for (int j = 0; j < n; j++)
		{
			dp[i][j] = 1000000000;
		}	
	}
	dp[1][0] = 0;
	for (int mask = 3; mask < (1 << n); mask++)
	{
		for (int r = 0; r < n; r++)
		{
			if ((mask & (1 << r)))
			for (int l = 0; l < n; l++)
			{
				if ((mask & (1 << l)) != 0 && w[l][r] != 0)
				{
					dp[mask][r] = min(dp[mask][r], dp[mask ^ (1 << r)][l] + w[l][r]);
				}

			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (w[i][0] == 0) continue;
		if (dp[(1 << n) - 1][i]+w[i][0] < minn) minn = dp[(1 << n) - 1][i]+w[i][0];
		//cout << dp[(1 << n) - 1][i] + w[i][0] << " ";
	}
	if (minn != 1000000000)
		cout << minn;
	else cout << "Nu exista solutie";
	return 0;
}