#include<fstream.h>
#include<stdlib.h>
#include<time.h>
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
	
time_t start;
int n,min=-1, sel[20],lista[20][20][2];
int contor = 0;
void Hamilton (int i,int j, int &cost)
{
	int k;
	contor++;
	if( contor % 10000 == 0)
	{
		if( ((double)clock() - start) / CLOCKS_PER_SEC > 1.1 )
		{
			g<<min<<"\n";
			exit(0);
		}
	}
		
	if (j==n)
	{
		for(k=1;k<=lista[i][0][0];k++)
		{
			if (lista[i][k][0]==1)
			{
				if (min<0)
					min=cost+lista[i][k][1];
				if (min > cost +lista[i][k][1])
					min=cost+lista[i][k][1];
				
			}
			
		}
		return;
	}
	else 
	{
		sel[i]=1;
		for (k=1;k<=lista[i][0][0];k++)
		{
			if(sel[lista[i][k][0]]==0)
			{
				int m=lista[i][k][0];
				int v=lista[i][k][1];
				cost=cost+v;
				Hamilton (m,j+1,cost);
				cost=cost-v;
			}
		}
		sel[i]=0;
	}
}
int main ()
{
	int i,j,k;
	f>>n;
	f>>k;
	while(f>>i>>j>>k)
	{
		lista[i][++lista[i][0][0]][0]=j;
		lista[i][lista[i][0][0]][1]=k;
	}
	int cost=0;
	Hamilton (1,1,cost);
	if (min<0)
		g<<"nu exista ciclu";
	if (min>0)
		g<<min;
	f.close();
	g.close();
	return 0;
}