#include <algorithm>
#include <vector>

using namespace std;

#define MAX (1<<18)
#define INF (1<<29)

int cost[18][18];
vector <int> a[18];
vector <int> ::iterator it;

int dp[MAX][18];
int n,m;
int i,j,vecin;

int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=0;i<18;i++)
		for(j=0;j<18;j++)
			cost[i][j]=INF;
		
	for(i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		
		cost[x][y]=z;
		a[y].push_back(x);
	}
	
	for(i=0;i<(1<<n);i++)
		for(j=0;j<n;j++)
			dp[i][j]=INF;
	
	dp[1][0]=0;
	
	for(i=3;i<(1<<n);i++)
	{
		for(j=0;j<n;j++)
		{
			if((i&(1<<j))==0)
				continue;
			
			for(it=a[j].begin();it!=a[j].end();it++)
			{
				if(( (i-(1<<j)) & (1<<(*it)) )==0)
					continue;
				dp[i][j]=min(dp[i][j],dp[i-(1<<j)][*it]+cost[*it][j]);
			}
		}
	}
	
	int sol=INF;
	
	for(i=1;i<n;i++)
	{
		sol=min(sol,dp[(1<<n)-1][i]+cost[i][0]);
	}
		
	printf("%d\n",sol);
	
	return 0;
}