#include <cstdio>
#include <algorithm>
using namespace std;
int N, M, a, b, c, s, bit, d[19][19], dp[32777];
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			d[i][j] = (i == j ? 0 : 1 << 29);
		}
	}
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &a, &b, &c);
		bit ^= (1 << a) ^ (1 << b);
		d[a][b] = min(d[a][b], c);
		d[b][a] = min(d[b][a], c);
		s += c;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	fill(dp, dp + (1 << N), 1 << 30); dp[bit] = s;
	for (int i = bit - 1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < j; k++) {
				if (!((i >> j) & 1) && !((i >> k) & 1)) {
					dp[i] = min(dp[i], dp[i + (1 << j) + (1 << k)] + d[j][k]);
				}
			}
		}
	}
	printf("%d\n", dp[0]);
	return 0;
}
