#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 1000000007
#define NMAX 19
#define INF 0x3f3f3f3f

using namespace std;

FILE *fin = freopen("hamilton.in", "r", stdin);
FILE *fout = freopen("hamilton.out", "w", stdout);

typedef pair<int, int> pii;

vector<int> v[NMAX];
int cost[NMAX][NMAX], dp[NMAX][1 << NMAX];

int memo(int nod, int mask) {
	if (dp[nod][mask] != -1)
		return dp[nod][mask];

	dp[nod][mask] = INF;
	int i;
	for (i = 0; i < v[nod].size(); ++i) {
		if (mask&(1 << v[nod][i])) {
			if (v[nod][i] != 0 || mask == (1<<nod)+1)
				dp[nod][mask] = min(dp[nod][mask], memo(v[nod][i], mask ^ (1 << nod)) + cost[v[nod][i]][nod]);
		}
	}

	return dp[nod][mask];
}

int main() {
	int n, m, i, j, x, y, c, a, b;

	cin >> n >> m;

	for (i = 0; i < m; ++i) {
		cin >> x >> y >> c;

		v[y].push_back(x);
		cost[x][y] = c;
	}

	memset(dp, -1, sizeof(dp));

	dp[0][1] = 0;
	int res = INF;
	for (i = 0; i < v[0].size(); ++i)
		res = min(res, memo(v[0][i], ((1 << n) - 1)) + cost[v[0][i]][0]);

	cout << res;

	return 0;
}