C++ :

#include <stdio.h>
#include <string.h>

#define inf 1000000000

int n, l, g[16][16], deg[16], odd[16], flag[16];

int dfs() {
	int i, j, t, r = inf;
	for (i = 0; i < l; i++)
		if (!flag[i])
			break;
	if (i == l)
		return 0;
	flag[i] = 1;
	for (j = i + 1; j < l; j++)
		if (!flag[j]) {
			flag[j] = 1;
			t = dfs() + g[odd[i]][odd[j]];
			r = r < t ? r : t;
			flag[j] = 0;
		}
	flag[i] = 0;
	return r;
}

int main() {
	int m, i, j, k, s, e, v, d;
	while (scanf("%d", &n) != EOF, n) {
		scanf("%d", &m);
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				g[i][j] = inf;
		memset(deg, 0, sizeof(deg));
		for (d = i = 0; i < m; i++) {
			scanf("%d%d%d", &s, &e, &v);
			deg[s]++;
			deg[e]++;
			d += v;
			if (v < g[s][e])
				g[s][e] = g[e][s] = v;
		}
		for (k = 1; k <= n; k++)
			for (i = 1; i <= n; i++)
				for (j = 1; j <= n; j++)
					if (g[i][k] + g[k][j] < g[i][j])
						g[i][j] = g[i][k] + g[k][j];
		for (l = 0, i = 1; i <= n; i++)
			if (deg[i] % 2)
				odd[l++] = i;
		memset(flag, 0, sizeof(flag));
		printf("%d\n", d + dfs());
	}
	return 0;
}