#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
const int INF = (1 << 30) - 1;

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

class Graph
{
private:
	//number of nodes
	int n;
	//number of edges
	int e;
	bool oriented = true;
	//adj list for graph representation
	vector<vector<int>> adj_list;
public:
	Graph() {}
	Graph(int n, bool oriented)
	{
		this->n = n;
		this->e = 0;
		this->oriented = oriented;
		//populate adj list with empty vectors
		vector<int> empty;
		for (int i = 0; i < n; i++)
		{
			this->adj_list.push_back(empty);
		}
	}
	virtual ~Graph() {}

	int hamilton_cycle_min_cost()
	{
		vector<vector<pair<int, int> >> adj_list_with_cost;
		vector<pair<int, int>> empty;
		for (int i = 0; i < this->n; i++)
		{
			adj_list_with_cost.push_back(empty);
		}
		int edges;
		fin >> edges;
		this->e = edges;
		for (int i = 0; i < this->e; i++)
		{
			int n1, n2, cost;
			fin >> n1 >> n2 >> cost;
			adj_list_with_cost[n1].push_back(make_pair(n2, cost));

		}

		int answer = INF;
		int nr_nodes = 1 << this->n;


		vector<int> v(this->n, INF);
		vector<vector<int>> costs(nr_nodes, v);

		costs[1][0] = 0;

		for (int i = 0; i < nr_nodes; i++)
		{
			for (int j = 0; j < this->n; j++)
			{
				if (i & (1 << j))
				{
					for (int k = 0; k < adj_list_with_cost[j].size(); k++)
					{
						if (i & (1 << adj_list_with_cost[j][k].first))
						{
							costs[i][j] = min(costs[i][j], costs[i ^ (1 << j)][adj_list_with_cost[j][k].first] + adj_list_with_cost[j][k].second);
						}
					}
				}
			}
		}

		for (int i = 0; i < adj_list_with_cost[0].size(); i++)
		{
			answer = min(answer, costs[nr_nodes - 1][adj_list_with_cost[0][i].first] + adj_list_with_cost[0][i].second);
		}
		return answer;


	}
};

int main()
{

	int n;
	fin >> n;
	Graph graph(n, true);
	int result = graph.hamilton_cycle_min_cost();
	if (result == INF)
	{
		fout << "Nu exista solutie";
	}
	else
	{
		fout << result;
	}

	return 0;
}