#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
	int x = 0, fh = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * fh;
}

void File() {
#ifdef zjp_shadow
	freopen ("connect.in", "r", stdin);
	freopen ("connect.out", "w", stdout);
#endif
}

const int N = 16;

int n, m, sumw;
int dp[N][1 << N], sum[1 << N], G[N][N], num[1 << N];

#define lowbit(x) (x & -x)

#define Get(i, v, k) for(register int sta = k, i = lowbit(sta), v = num[i]; sta; sta ^= i, v = num[i = lowbit(sta)])

int main () {

	File(); Set(dp, 0);

	n = read(); m = read();

	For (i, 0, n - 1) num[1 << i] = i;
	For (i, 1, m) { 
		int u = read() - 1, v = read() - 1, w = read(); G[u][v] = G[v][u] = w; sumw += w; 
	}

	int maxsta = (1 << n) - 1;

	For (i, 1, maxsta) {
		register int u = num[lowbit(i)];
		sum[i] = sum[i ^ lowbit(i)];
		Get(j, v, i) sum[i] += G[u][v];
	}

	Set(dp, -0x7f);
	for (int i = 1; i <= maxsta; i += 2) {
		dp[0][i] = sum[i];
		For (S, 0, n - 1) if (dp[S][i] >= 0) {
			int rest = maxsta ^ i;
			for (register int sub =	rest; sub; (-- sub) &= rest)
				chkmax(dp[S][i | sub], dp[S][i] + sum[sub ^ (1 << S)]);
			Get(j, v, rest)
				chkmax(dp[v][i | j], dp[S][i] + G[S][v]);
		}
	}
	printf ("%d\n", sumw - dp[n - 1][maxsta]);

	return 0;
}