#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int mat[N][N], inside[1 << N], cross[1 << N][N], f[1 << N][N];
int main()
{
	int n, m;
	cin >> n >> m;
	while (m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		mat[u - 1][v - 1] = mat[v - 1][u - 1] = w;
	}
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (i & (1 << j))
				for (int k = 0; k < j; k++)
					if (i & (1 << k))
						inside[i] += mat[j][k];
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (!(i & (1 << j)))
				for (int k = 0; k < n; k++)
					if (i & (1 << k))
						cross[i][j] += mat[j][k];
	fill_n(&f[0][0], sizeof(f) / sizeof(int), -1);
	f[1][0] = 0;
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (~f[i][j])
			{
				for (int k = 0; k < n; k++)
					if (!(i & (1 << k)) && mat[j][k])
						f[i | (1 << k)][k] = max(f[i | (1 << k)][k], f[i][j] + mat[j][k]);
				int c = (1 << n) - i - 1;
				for (int s = c; s; s = (s - 1) & c)
					f[i | s][j] = max(f[i | s][j], f[i][j] + inside[s] + cross[s][j]);
			}
	cout << inside[(1 << n) - 1] - f[(1 << n) - 1][n - 1] << endl;
	return 0;
}