using namespace std;
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using pii = pair<int, int>;
#define INF 1e9
#define Nmax 18

int n, d[1 << Nmax][Nmax];
int cost[Nmax][Nmax];
vector< int > G[Nmax];

void calc(int, int);
void read();
void write(int);

int main()
{
	int i, j, min_c;

	read();

	if (n == 1)
	{
		write(0);
		return 0;
	}

	for (i = 0; i < (1 << n); ++i)
		for (j = 0; j < n; ++j)
			d[i][j] = -1;

	d[1][0] = 0;

	for (min_c = INF, i = 0; i < n; ++i)
		if(cost[i][0])
	{
		calc((1 << n) - 1, i);

		min_c = min(min_c, d[(1 << n) - 1][i] + cost[i][0]);
	}

	write(min_c);

    return 0;
}

void calc(int nodes, int last_node)
{
	if (d[nodes][last_node] != -1) return;

	d[nodes][last_node] = INF;
	if ((nodes & (1 << last_node)) == 0) return;
	if ((nodes & 1) == 0) return;

	for (auto &j : G[last_node])
		if ((nodes & (1 << j)) && cost[j][last_node] > 0)
		{
			calc(nodes ^ (1 << last_node), j);

			d[nodes][last_node] = min(d[nodes][last_node], d[nodes ^ (1 << last_node)][j] + cost[j][last_node]);
		}

	// cout << nodes << ' ' << last_node << ' ' << d[nodes][last_node] << '\n';
}

void read()
{
	int m, x, y, z;
	ifstream fin("hamilton.in");

	fin >> n;

	for (fin >> m; m; --m)
	{
		fin >> x >> y >> z;

		G[y].push_back(x);

		cost[x][y] = z;
	}

	fin.close();
}

void write(int ans)
{
	ofstream fout("hamilton.out");

	if(ans != INF && ans != -1) fout << ans << '\n';
	else fout << "Nu exista solutie\n";

	fout.close();
}