#include <fstream>
#define INF 100000000
using namespace std;

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

void gen (int k);
void test ();
void citire ();
void afisare ();

int c, n, m, cmin=INF;
int v[20], vmin[20], cost[20][20], car[20];

int main()
{
 citire ();
 vmin[1]=1; v[1]=1;
 gen (2);
 if (cmin!=INF)
		afisare ();
	else
		fout<<"Nu exista solutie";
    fin.close ();
    fout.close ();
    return 0;
}

void gen (int k)
{
	int i;
	if (k==n+1)
	{
		if (cost[v[n]][1])
			{
				c+=cost[v[n]][1];
				test ();
				c-=cost[v[n]][1];
			}
	}
	else
	{
		for (i=2; i<=n; i++)
			if ((cost[v[k-1]][i])&&(!car[i]))
				{
					v[k]=i;
					c+=cost[v[k-1]][i];
					car[i]=1;
					gen (k+1);
					c-=cost[v[k-1]][i];
					car[i]=0;
				}
	}
}

void test ()
{
	int i;
	if (c<cmin)
	{
		cmin=c;
		for (i=2; i<=n; i++)
			vmin[i]=v[i];
	}
}

void citire ()
{
	fin>>n>>m;
	int i, x, y, z;
	for (i=1; i<=m; i++)
		{
			fin>>x>>y>>z;
			cost[x+1][y+1]=z;
			//cost[y][x]=z;
		}
}

void afisare ()
{
	int i;
	fout<<cmin;
}