UVa 10296 - Jogging Trails

// UVa 10296 - Jogging Trails

#include <iostream>
#include <string.h>
using namespace std;

int n, m, oo;
int lnk[16][16], dist[16][16], T[65536];

void floyd() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dist[i][j] = lnk[i][j];
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			if (dist[i][k] != oo)
				for (int j = 1; j <= n; j++)
					if (dist[i][j] > dist[i][k] + dist[k][j])
						dist[i][j] = dist[i][k] + dist[k][j];
}

int dp(int mask) {
	if (T[mask] == oo) {
		int partial = oo;
		for (int i = 1; i <= n; i++)
			if (mask & (1 << i)) {
				for (int j = 1; j <= n; j++)
					if (j != i && (mask & (1 << j))) {
						int new_mask = ((mask ^ (1 << i)) ^ (1 << j));
						int sub = dp(new_mask);
						if (sub + dist[j][i] < partial)
							partial = sub + dist[j][i];
					}
			}
		T[mask] = partial;
	}
	return T[mask];
}

int main() {
	while ((cin >> n) && n) {
		cin >> m;
		int total_sum = 0;
		memset(lnk, 127, sizeof(lnk));
		oo = lnk[0][0];
		int cnt[16];
		memset(cnt, 0, sizeof(cnt));
		// input
		for (int j = 0; j < m; j++) {
			int a, b, c;
			cin >> a >> b >> c;
			total_sum += c;
			if (lnk[a][b] > c) {
				lnk[a][b] = c;
				lnk[b][a] = c;
			}
			cnt[a]++;
			cnt[b]++;
		}
		// prepare
		floyd();
		int start = 0;
		for (int i = 1; i <= n; i++)
			if (cnt[i] & 1)
				start = start | (1 << i);
		// DP
		memset(T, 127, sizeof(T));
		T[0] = 0;
		cout << total_sum + dp(start) << endl;
	}
	return 0;
}