#include <cstring>
#include <cstdio>
int val[15][15], sum[100005], dp[100005][15]; 
inline void upd(int &x, int y)
{
	if (x < y)
		x = y; 
}
int main()
{
	// freopen("ARC078-F.in", "r", stdin); 
	int n, m; 
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int u, v, w; 
		scanf("%d%d%d", &u, &v, &w); 
		val[--u][--v] = w; 
		val[v][u] = w; 
	}
	for (int i = 0; i < 1 << n; i++)
	{
		for (int x = 0; x < n; x++)
		{
			for (int y = x; y < n; y++)
			{
				if ((i & (1 << x)) && (i & (1 << y)))
					sum[i] += val[x][y]; 
			}
		}
	}
	memset(dp, -0x3f, sizeof(dp)); 
	dp[1][0] = 0; 
	for (int s = 0; s < 1 << n; s++)
	{
		for (int i = 0; i < n; i++)
		{
			if (!(s & (1 << i)))
				continue; 
			for (int j = 0; j < n; j++)
			{
				if ((s & (1 << j)) || !val[i][j])
					continue; 
				upd(dp[s | (1 << j)][j], dp[s][i] + val[i][j]); 
			}
			int x = (1 << n) - 1 ^ s; 
			for (int t = x; t; t = t - 1 & x)
				upd(dp[s | t][i], dp[s][i] + sum[t | (1 << i)]); 
		}
	}
	printf("%d\n", sum[(1 << n) - 1] - dp[(1 << n) - 1][n - 1]);
	return 0; 
}
