#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

#define IPair pair<int,int>
#define ull unsigned long long

int N, M;
ull finishNumber;

struct node
{
	int last_node;
	int cost;
	bitset<32> visits;
	node(int last_node, int cost, bitset<32> visits) : last_node(last_node), cost(cost), visits(visits) {}

	//vector<int> path;
	//node(int last_node, int cost, bitset<32> visits, vector<int> path) : last_node(last_node), cost(cost), visits(visits), path(path) {}
	int size;
	node setSize(int newSize)
	{
		size = newSize;
		return (*this);
	}
};

struct CompareNode
{
	int operator()(const node& a, const node& b)
	{
		return a.cost > b.cost;
	}
};

int solve(vector<vector<IPair>>& links)
{
	priority_queue<node, vector<node>, CompareNode> pq;
	pq.push(node(
		0, 0, bitset<32>(0)/*, vector<int>()*/
	).setSize(1));

	int minCost = INT32_MAX - 100;

	while (!pq.empty())
	{
		node nod = pq.top();
		pq.pop();

		if (minCost < nod.cost)
		{
			continue;
		}



		bool finished = (nod.size == N + 1);

		if (finished)
		{
			if (nod.last_node != 0) continue;
			if (minCost > nod.cost)
			{
				minCost = nod.cost;
			}
		}
		else
		{
			if (nod.last_node == 0 && nod.size != 1) continue;
			for (auto it = links[nod.last_node].begin(); it != links[nod.last_node].end(); it++)
			{
				int destination = it->first;
				int cost = it->second;
				if (!nod.visits[destination])
				{
					bitset<32> newVisits = nod.visits;
					newVisits[destination] = true;

					/*vector<int> newPath = nod.path;
					newPath.push_back(destination);*/

					pq.push(node(
						destination, nod.cost + cost, newVisits/*, newPath*/
					).setSize(nod.size + 1));
				}
			}
		}
	}

	return minCost;
}

int main()
{
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	// Program
	f >> N >> M;
	vector<vector<IPair>> links(M, vector<IPair>());

	bitset<32> finishedNumberSet;
	for (int i = 0; i < N; i++)
	{
		finishedNumberSet[i] = 1;
	}
	finishNumber = finishedNumberSet.to_ullong();
		
	for (int i = 0; i < M; i++)
	{
		int source, destination, cost;

		f >> source >> destination >> cost;
		links[source].push_back(make_pair(destination, cost));
	}

	g << solve(links);

	// Exit
	f.close();
	g.close();
	return 0;
}