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

using namespace std;

template<class T>
void print_vector(ostream &os, const vector<T> &v)
{
	for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) {
		if (it != v.begin())
			os << ' ';
		os << *it;
	}
	os << endl;
}

template<class T>
ostream & operator <<(ostream &os, const vector<T> &v)
{
	unsigned int i = 0;
	for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) {
		os << i << ": ";
		print_vector(os, *it);
		i++;
	}
	return os;
}

void read_input(const char *filename, vector< vector< pair<int, int> > > &neighbour_list)
{
	ifstream f(filename);
	int n, m;

	f >> n >> m;
	for (int i = 0; i < n; i++)
		neighbour_list.push_back(vector< pair<int, int> >());
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		f >> x >> y >> cost;
		neighbour_list[y].push_back(pair<int, int>(x, cost));
	}

	f.close();
}

void write_output(const char *filename, long long result)
{
	ofstream f(filename);

	f << result << endl;

	f.close();
}

long long solve_problem(const vector< vector< pair<int, int> > > &neighbour_list)
{
	vector< vector<long long> > dp;
	long long result = numeric_limits<long long>::max();
	const size_t num_nodes = neighbour_list.size();
	const size_t num_masks = 1U << num_nodes;

	for (size_t i = 0; i < num_masks; i++)
		dp.push_back(vector<long long>(num_nodes, numeric_limits<long long>::max()));
	dp[1][0] = 0;

	for (size_t i = 1; i < num_masks; i++) {
		for (size_t j = 0; j < num_nodes; j++) {
			unsigned int mask = 1U << j;
			if (i & mask) {
				size_t k = i & ~mask;
				const vector< pair<int, int> > &n_list = neighbour_list[j];
				for (vector< pair<int, int> >::const_iterator it = n_list.begin();
						it != n_list.end(); ++it) {
					pair<int, int> elem = *it;
					int node = elem.first;
					if (k & (1U << node)) {
						long long candidate = dp[k][node];
						if (candidate < numeric_limits<long long>::max()) {
							candidate += elem.second;
							dp[i][j] = min(dp[i][j], candidate);
						}
					}
				}
			}
		}
	}

	const vector< pair<int, int> > &n_list = neighbour_list.front();
	const vector<long long> &final_dp = dp.back();
	for (vector< pair<int, int> >::const_iterator it = n_list.begin();
			it != n_list.end(); ++it) {
		pair<int, int> elem = *it;
		long long sum = final_dp[elem.first];
		if (sum < numeric_limits<long long>::max())
			sum += elem.second;
		result = min(sum, result);
	}

	return result;
}

int main()
{
	vector< vector< pair<int, int> > > neighbour_list;
	long long result;

	read_input("hamilton.in", neighbour_list);
	result = solve_problem(neighbour_list);
	write_output("hamilton.out", result);

	return 0;
}