#include <stdio.h>
int x,y,z,j,k,n,m,dp[(1<<19)][19],i,min;
int a[19][19];
int main(void)
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
	}
	for (j=1;j<(1<<n);j++)
	{
		for (i=0;i<n;i++)
		{
			dp[j][i]=1000000000;
		}
	}
	dp[1][0]=0;
	for (j=1;j<(1<<n);j++)
	{
		for (i=0;i<n;i++)
		{
			if (!(j&(1<<i))) continue;
			for (k=0;k<n;k++)
			{
				if (!(j&(1<<k)) || k==i) continue;
				if (!a[k][i]) continue;
				if (dp[j][i]>dp[j^(1<<i)][k]+a[k][i]) dp[j][i]=dp[j^(1<<i)][k]+a[k][i];
			}
		}
	}
	min=1000000000;
	for (i=1;i<n;i++)
		if (min>dp[(1<<n)-1][i]+a[i][0] && a[i][0]) min=dp[(1<<n)-1][i]+a[i][0];
	printf("%d\n",min);
	return 0;
}