#include <fstream>
#include <cstring>
#define NMAX 100
#define INF 99999999

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

void citire();
void bkt(int k);
void afisare();

bool uz[NMAX];
int n, m;
int lgt, lgmin = INF;
int t[NMAX], tmin[NMAX];
int a[NMAX][NMAX];

int main()
{
	citire();
	t[1] = 1;
	uz[1] = 1;
	bkt(2);
	afisare();
	return 0;
}

void citire()
{
	int i, x, y, l;

	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> l;
		a[x+1][y+1] = l;
	}
}

void bkt(int k)
{
	int i;

	if (k == n + 1)
	{
		if (a[t[n]][1])
		{
			if (lgt + a[t[n]][1] < lgmin)
			{
				lgmin = lgt + a[t[n]][1];
				memcpy(tmin, t, sizeof(t));
			}
		}
	}
	else
	{
		for (i = 1; i <= n;i++)
			if (!uz[i] && a[t[k - 1]][i])
			{
				t[k] = i;
				lgt += a[t[k - 1]][i];
				uz[i] = 1;
				bkt(k + 1);
				uz[i] = 0;
				lgt -= a[t[k - 1]][i];
			}
	}
}

void afisare()
{
	if (lgmin == INF)
		fout << "Nu exista solutie\n";
	else
		fout << lgmin << '\n';
}