#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n, m, i, j, k, dp[524288][19],cost[19][19],x,y,mask,mini=1e9;
int main() {
	ifstream cin("hamilton.in");
	ofstream cout("hamilton.out");
	cin >> n >> m;
	for (i = 1;i <= m;i++)
	{
		cin >> x >> y;
		x++;
		y++;
		cin>>cost[x][y];
	}
	for(mask=1;mask<=(1<<(n))-1;mask++)
		for(i=1;i<=n;i++)
			if(((1<<(i-1)) & mask)!=0)
		for(j=1;j<=n;j++)
			if(j!=i)
			if (((1<<(j-1)) & mask) != 0) {
				{
					if (cost[j][i] == 0) cost[j][i] = 1e9;
					if (dp[mask][i] == 0) dp[mask][i] = 1e9;
					dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << (i-1))][j] + cost[j][i]);
				}
			}
	for (i = 2;i <= n;i++)
		mini = min(mini,dp[(1 << n) - 1][i] + cost[i][1]);
	cout << mini;
}