#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define SZ(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
#define repe(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
const int INF = 0x3f3f3f3f;
int edge[15][15];
int dp[1 << 15][15];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	rep (i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		edge[u - 1][v - 1] = w;
		edge[v - 1][u - 1] = w;
	}
	memset(dp, 0x3f, sizeof(dp));
	rep (msk, 0, (1 << n) - 1) {
		if (!(msk & 1)) continue;
		if (msk >> (n - 1) & 1) continue;
		dp[msk][0] = 0;
		rep (i, 0, n - 1) if (msk >> i & 1) {
			rep (j, 0, n - 1) if (!(msk >> j & 1)) {
				dp[msk][0] += edge[i][j];
			}
		}
	}
	rep (msk, 0, (1 << n) - 1) {
		rep (u, 0, n - 1) if (dp[msk][u] != INF) {
			int las = (1 << n) - 1 - msk;
			for (int nmsk = las; nmsk; nmsk = (nmsk - 1) & las) {
				rep (v, 0, n - 1) if ((nmsk >> v & 1) && edge[u][v]) {
					int rmsk = msk | nmsk;
					int ndpv = dp[msk][u] - edge[u][v];
					rep (i, 0, n - 1) if (nmsk >> i & 1) {
						rep (j, 0, n - 1) if (!(rmsk >> j & 1)) {
							ndpv += edge[i][j];
						}
					}
					dp[rmsk][v] = min(dp[rmsk][v], ndpv);
				}
			}
		}
	}
	int res = INF;
	rep (msk, 0, (1 << n) - 1) {
		res = min(res, dp[msk][n - 1]);
	}
	cout << res << endl;
	return 0;
}