#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 20, INF = 1e9;

int n, m, x, y, c;

int G[MAXN][MAXN], sum[1 << MAXN];
int dp[1 << MAXN][MAXN];

int cost(int x, int y) {
	return sum[x | y] - (sum[x] + sum[y]);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &x, &y, &c); x--; y--;
		G[x][y] = c;
		G[y][x] = c;
	}

	for (int i = 0; i < 1 << n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (((i >> j)&1) == 0) continue;
			for (int k = j+1; k < n; ++k) {
				if ((i >> k)&1)	sum[i] += G[j][k];
			}
		}
	}

	for (int i = 0; i < 1 << n; ++i) {
		for (int j = 0; j < n; ++j) {
			dp[i][j] = INF;
		}
	}
	dp[1][0] = 0;

	for (int i = 0; i < 1 << n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (dp[i][j] == INF) continue;
			for (int k = 0; k < n; ++k) {
				if ((i >> k) & 1) continue;
				if (G[j][k] == 0) continue;
				dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], 
						dp[i][j] + cost(i ^ (1 << j), 1 << k));
			}
			for (int k = ((1 << n)-1) & ~i; k > 0; k = (k-1)& ~i) {
				dp[i | k][j] = min(dp[i | k][j], dp[i][j] + cost(i ^ (1 << j), k));
			}
		}
	}

	printf("%d\n", dp[(1 << n)-1][n-1]);


	return 0;
}
