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

using namespace std;

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

const int NMAX = 20;
int c[NMAX][NMAX], dp[1 << NMAX][NMAX];
vector <int> in[NMAX];

int main() {
	int n, m, x, y, z;
	fin >> n >> m;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			c[i][j] = 1e9;
	for (int i = 0; i < m; i++) {
		fin >> x >> y >> z;
		in[y].push_back(x);
		c[x][y] = z;
	}
	for (int i = 1; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = 1e9;
	dp[1][0] = 0;
	for (int mask = 1; mask < (1 << n); mask++) {
		for (int i = 1; i < n; i++) {
			if (mask & (1 << i)) {
				for (int k = 0; k < in[i].size(); k++) {
					int j = in[i][k];
					dp[mask][i] = min(dp[mask][i], dp[mask - (1 << i)][j] + c[j][i]);
				}
			}
		}
	}
	int res = 1e9;
	for (int i = 1; i < n; i++)
		res = min(res, dp[(1 << n) - 1][i] + c[i][0]);
	if (res != 1e9)
		fout << res;
	fin.close();
	fout.close();
	return 0;
}