#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define INF 20000000

struct T
{
	T(int i, int j, int c)
	{
		x = i;
		y = j;
		this->c = c;
	}

	int x, y, c;
};

vector<T> a;
int n, N, m, i;

void init();
int cost(int, int);

int main()
{
	init();
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);

	cin >> n >> m;
	int x, y, z;
	for(i=0;i<m;++i)
	{
		cin >> x >> y >> z;
		a.push_back(T(x, y, z));
	}
	N = (1 << (n - 1)) - 1;

	bool found = 0;
	int min = INF, aux;
	for(i=0;i<m;++i)
		if(a[i].y == 0)
		{
			aux = cost(a[i].x, N) + a[i].c;
			if(aux < INF)
				found = true,
				min = std::min(min, aux);
		}

	if (!found)
	    cout << "Nu exista solutie" << endl;
	else
	    cout << min << endl;

	return 0;
}

int c[17][1<<17];

void init()
{
	memset(c, -1, sizeof(c));
}

int cost(int v, int N)
{
	if(c[v][N] == -1)
	{
		c[v][N] = INF;
		int p = 1 << (v - 1), i, j;

		if(N == p)
		{
			for(i=0;i<m;++i)
				if(a[i].x == 0 && a[i].y == v)
					c[v][N] = min(c[v][N], a[i].c);
		}
		else
		{
			for(i=0;i<m;++i)
			{
				j = 1 << (a[i].x - 1);
				if(a[i].y == v && (N & j))
					c[v][N] = min(c[v][N], cost(a[i].x, N - p) + a[i].c);
			}
		}
	}

	return c[v][N];
}