#include <iostream>
#include <vector>
#include <functional>
#include <limits.h>
#define MAX_N 18

using namespace std;
vector<pair<char, int> > edges[MAX_N];
int dp[1 << 18][MAX_N]; // last node

int main()
{
	FILE *fin = fopen("hamilton.in", "r");
	FILE *fout = fopen("hamilton.out", "w");
	int n, m;
	fscanf(fin, "%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		fscanf(fin, "%d %d %d", &a, &b, &c);
		edges[a].push_back({b, c});
	//	edges[b].push_back({a, c});
	}
	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = INT_MAX;
	dp[0][0] = 0;
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] == INT_MAX)
				continue;
			for (auto k: edges[j]) {
	  			int nxt = k.first;
				if (((1 << nxt) & i) != 0)
					continue;
				int neww = i | (1 << nxt);
				if (nxt == 0 && neww != ((1 << n) - 1))
					continue;
				//printf("%d %d %d\n", nxt, i | (1 << nxt), j);
				dp[neww][nxt] = min(dp[neww][nxt], dp[i][j] + k.second);
				
			}

		}
	}
	if (n == 1) {
		fprintf(fout, "%d\r\n", 0);
		return 0;
	}
	//printf("alyo\n");
	int result = INT_MAX;
	for (int i = 0; i < n; i++)
		result = min(result, dp[(1 << n) - 1][i]);
	if (result != INT_MAX)
		fprintf(fout, "%d\n", result);
	else
		fprintf(fout, "Nu exista solutie\n");
}