#include <fstream>
#define IN "hamilton.in"
#define OUT "hamilton.out"
#define DMAX 100
#define INF 100000000
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int n, m;
int c[DMAX][DMAX];
int sol[DMAX], cost;
int solmin[DMAX], costmin=INF;
int uz[DMAX];
int di[DMAX];

void citire();
void init();
void bkt(int);

int main(int argc, const char * argv[])
{
	int i;
	citire();
	sol[1]=1;
	uz[1]=1;
	bkt(2);
	//for (i=1; i<=n; ++i)
		//fout <<solmin[i]<<' ';
	//fout <<solmin[1]<<'\n';
	if (costmin<INF)
		fout <<costmin<<'\n';
	else
		fout <<"Nu exista solutie\n";
	fout.close();
    return 0;
}

void bkt(int k)
{
	int i;
	if (cost>costmin) return;
	if (k>n)
	{
		cost+=c[sol[k-1]][sol[1]];
		if (cost<costmin)
		{
			for (i=1; i<=n; ++i)
				solmin[i]=sol[i];
			costmin=cost;
		}
		cost-=c[sol[k-1]][1];
	}
	
	for (i=1; i<=n; ++i)
		if (!uz[i] && c[sol[k-1]][i]<INF)
		{
			uz[i]=1;
			sol[k]=i;
			cost+=c[sol[k-1]][i];
			bkt(k+1);
			uz[i]=0;
			cost-=c[sol[k-1]][i];
		}
}

void citire()
{
	int i, a, b, cost;
	
	fin >>n>>m;
	init();
	for (i=1; i<=m; ++i)
	{
		fin >>a>>b>>cost;
		++a; ++b;
		di[b]++;
		di[a]++;
		c[a][b]=cost;
	}
	
}

void init()
{
	int i, j;
	
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			c[i][j]=INF;
	
	for (i=1; i<=n; i++)
		c[i][i]=0;
}