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

using namespace std;

#define IPair pair<int,int>

int N, M;

// int [destinationNode][mask] = cost
int matrix[20][262200];
// 262144 = 2^18
int solveMask = 0;
int nearlySolvedMask = 0;
int solve(vector<vector<IPair>>& links, int node, int mask)
{
	if (node == 0 && mask == solveMask)
	{
		return 0;
	}

	if (matrix[node][mask] == 0)
	{
		matrix[node][mask] = INT32_MAX /2;
		for (auto it = links[node].begin(); it != links[node].end(); it++)
		{
			int destination = it->first;
			if (destination == 0 && mask != nearlySolvedMask) continue;

			int testVisitMask = 1 << destination;
			if (mask & testVisitMask)
			{
				// visited
			}
			else
			{
				int cost = it->second;
				matrix[node][mask] = min(matrix[node][mask], cost + solve(links, destination, mask | testVisitMask));
			}
		}
	}

	return matrix[node][mask];
}

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

	for (int i = 0; i < N; i++)
	{
		solveMask = (solveMask << 1) | 1;
	}
	nearlySolvedMask = solveMask - 1;

	for (int i = 0; i < M; i++)
	{
		int source, destination, cost;

		f >> source >> destination >> cost;
		links[source].push_back(make_pair(destination, cost));
	}
	
	int result = solve(links, 0,0);
	if (result == INT32_MAX / 2)
	{
		g << "Nu exista solutie";
	}
	else
	{
		g << result;
	}

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