#include <bits/stdc++.h>

const int N = 15, inf = 0x3f3f3f3f;

int n, m, e[N][1 << N], dp[N][1 << N], sum[1 << N], mask;

#define ctz __builtin_ctz
#define for_bit(i, s) for (int _##i = s, i = ctz(_##i); _##i; i = ctz(_##i = _##i & _##i - 1))

void down(int &x, int y) { x = std::min(x, y); }
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> m, mask = ~(-1 << n);
	for (int i = 0, x, y, z; i < m; ++i)
		std::cin >> x >> y >> z, --x, --y, e[x][1 << y] = e[y][1 << x] = z;
	for (int i = 0; i < n; ++i)
		for (int j = 1; j < 1 << n; ++j)
			e[i][j] = e[i][j & -j] + e[i][j & j - 1];
	std::memset(dp, 0x3f, sizeof dp), dp[0][1] = 0;
	for (int s = 0; s <= mask; ++s)
		for_bit(i, s) if (dp[i][s] != inf) {
			int v = dp[i][s], c = mask ^ s;
			if (i != n - 1) for_bit(j, c) if (e[i][1 << j]) down(dp[j][s | 1 << j], v + e[j][s ^ 1 << i]);
			for (int p = c & c - 1; ; p = p - 1 & c) {
				int q = c ^ p; sum[q] = sum[q & q - 1] + e[ctz(q)][s ^ 1 << i];
				if (!p) break;
			}
			for (int p = c; p; p = p - 1 & c) down(dp[i][s | p], v + sum[p]);
		}
	std::cout << dp[n - 1][mask] << '\n';
	return 0;
}