#include <cstdio>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 15;
const int inf = 0x3f3f3f3f;

int mmap[maxn][maxn];
LL in[1 << maxn];
LL dp[1 << maxn][maxn];
int n, m;

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, f, t, d; i < m; ++i)
	{
		scanf("%d%d%d", &f, &t, &d);
		mmap[t - 1][f - 1] = mmap[f - 1][t - 1] = d;
	}
	for (int i = 0; i < (1 << n); ++i)
		for (int j = 0; j < n; ++j)
			if (i & (1 << j))
				for (int k = j + 1; k < n; ++k)
					if (i & (1 << k))
						in[i] += mmap[j][k];
	for (int i = 0; i < (1 << n); ++i)
		for (int j = 0; j < n; ++j)
			dp[i][j] = -inf;
	for (int i = 0; i < (1 << n); ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (i & (1 << j))
			{
				if (!j)
					dp[i][j] = in[i];
				else
				{
					for (int k = 0; k < n; ++k)
						if (j != k && (i & (1 << k)) && mmap[k][j])
							dp[i][j] = max(dp[i][j], dp[i ^ (1 << j)][k] + mmap[k][j]);
					for (int tmp = (i ^ (1 << j)), k = tmp; k; k = (k - 1) & tmp)
						dp[i][j] = max(dp[i][j], dp[i ^ k][j] + in[k | (1 << j)]);
				}
			}
		}
	}
//	 cout << in[(1 << n) - 1] << endl;
	printf("%lld\n", in[(1 << n) - 1] - dp[(1 << n) - 1][n - 1]);
	return 0;
}
