#include <cstdio>
#include <fstream.h>
#include <cstring>
#define INF 20000000
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int c[20][20],mc[20][20],sol[(1<<18)+9][20];

inline int mi(int x,int y) {return ((x<y)? x:y);}

void rez(int secv,int l)
{
	int i;
	secv=secv^(1<<l);
	if (sol[secv][l]) return ;
	if (secv==0) return;
	sol[secv][l]=INF;
	for (i=1;i<=mc[l][0];++i)
		if (secv&(1<<mc[l][i]))
		{
			if ((mc[l][i]==0) && (secv!=(1<<0)))
				continue;
			rez(secv,mc[l][i]);
			sol[secv][l]=mi(sol[secv][l],sol[secv^(1<<mc[l][i])][mc[l][i]]+c[mc[l][i]][l]);
		}
}		


int main()
{
	int n,m,min=INF,i,j,x;
	f>>n>>m;
	while (m--)
	{ 
		f>>i>>j;
		f>>c[i][j];
		mc[j][++mc[j][0]]=i;
	}
	
	for (x=1;x<=mc[0][0];++x)
	{
		rez((1<<n)-1,mc[0][x]);
		min=mi(min,sol[((1<<n)-1)^(1<<mc[0][x])][mc[0][x]]+c[mc[0][x]][0]);
	}
	g<<min;
	f.close();
	g.close();
	
return 0;}