#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;

struct visitMask
{
	vector<bool> visits;
	int totalCount;
	visitMask(vector<bool> visits, int totalCount) : visits(visits), totalCount(totalCount) {}

	visitMask(visitMask ref, int node)
	{
		this->visits = ref.visits;
		this->visits[node] = true;
		this->totalCount = ref.totalCount + 1;
	}
};

ull solve(vector<vector<IPair>>& links, visitMask visits, int this_node)
{
	if (this_node == 0 && visits.totalCount == N + 1) return 0;

	ull minHam = INT64_MAX - 100;
	for (auto it = links[this_node].begin(); it != links[this_node].end(); it++)
	{
		int destination = it->first;
		if (!visits.visits[destination])
		{
			int cost = it->second;
			ull solveResult = solve(links, visitMask(visits, destination), destination) + cost;
			if (solveResult < minHam)
			{
				minHam = solveResult;
			}
		}
	}
	return minHam;
}

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

	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, visitMask(vector<bool>(N), 1), 0);

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