#include <bits/stdc++.h>

using namespace std;

const int nMax = 18;

const int INF = 1e8;

int n, m;
vector<pair<int, int>>g[nMax];
int dp[1 << nMax][nMax];

bool bit(int mask, int nod) {
	return mask & (1 << nod);
}

int main() {
	ifstream cin("hamilton.in");
	ofstream cout("hamilton.out");
	cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int from, to, cost;
		cin >> from >> to >> cost;
		g[to].emplace_back(from, cost);
	}

	for (int mask = 0; mask < 1 << n; ++mask)
		for (int i = 0; i < n; ++i)
			dp[mask][i] = INF;

	dp[1][0] = 0;

	for (int mask = 1; mask < 1 << n; ++mask) {
		for (int i = 0; i < n; ++i) {
			if (bit(mask, i)) {
				for (const auto &j : g[i]) {
					if (bit(mask, j.first)) {
						dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j.first] + j.second);
					}
				}
			}
		}
	}

	int ans = INF;
	for(const auto &j : g[0])
		ans = min(ans, dp[(1 << n) - 1][j.first] + j.second);

	cout << ans;
	return 0;
}