#define MAX_N 18
#define INF 0x3f3f3f3f

#define GET_BIT(mask, index) ((mask >> index) & 1)
#define SET_BIT(mask, index) (mask | (1 << index))
#define RESET_BIT(mask, index) (mask & (~(1 << index)))

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

struct A
{
	A(int _node, int _cost) : node(_node), cost(_cost)
	{
	}
	
	int node, cost;
};

int n, m, Dp[1 << MAX_N][MAX_N];
bool Comp[1 << MAX_N][MAX_N];

vector<A> Gt[MAX_N];

int BestCost(int mask, int endNode);

int main()
{
	fin >> n >> m;
	
	for (int i = 0; i < m; ++i)
	{
		int x, y, c;
		
		fin >> x >> y >> c;
		
		Gt[y].emplace_back(x, c);
	}
	
	int bestCost = BestCost((1 << n) - 1, 0);
	
	if (bestCost == INF)
	{
		fout << "Nu exista solutie";
	}
	else
	{
		fout << bestCost;
	}
	
	fin.close();
	fout.close();
	return 0;
}

int BestCost(int mask, int endNode)
{	
	if (!Comp[mask][endNode])
	{
		Comp[mask][endNode] = true;
		
		if (mask == SET_BIT(0, endNode))
		{
			if (0 != endNode)
			{
				int cost = INF;
				for (const auto& node : Gt[endNode])
				{
					if (0 == node.node)
					{
						cost = node.cost;
						break;
					}
				}
				
				Dp[mask][endNode] = cost;
			}
			else
			{
				Dp[mask][endNode] = 0;
			}
		}
		else
		{
			Dp[mask][endNode] = INF;
			for (const auto& node : Gt[endNode])
			{
				if (GET_BIT(mask, node.node) == 1)
				{
					int cand = BestCost(RESET_BIT(mask, endNode), node.node) + node.cost;
					
					if (Dp[mask][endNode] > cand)
					{
						Dp[mask][endNode] = cand;
					}
				}
			}
		}
	}
	
	return Dp[mask][endNode];
}