#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ii, ii> iii;
int MOD = 1e9 + 9;
const ld E = 1e-7;
#define null NULL
#define ms(x) memset(x, 0, sizeof(x))
#ifndef LOCAL
#define endl "\n"
#endif
#ifndef LONG_LONG_MAX
#define LONG_LONG_MAX LLONG_MAX
#endif
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define _read(x) freopen(x, "r", stdin)
#define _write(x) freopen(x, "w", stdout)
#define files(x) _read(x ".in"); _write(x ".out")
#define filesdatsol(x) _read(x ".DAT"); _write(x ".SOL")
#define output _write("output.txt")
#define input _read("input.txt")
#define prev time_prev
#ifndef M_PI
#define M_PI acos(-1)
#endif
#define remove tipa_remove
#define next tipa_next
#define left tipa_left
#define right tipa_right
#define mod % MOD
#define y1 hello_world
unsigned char ccc;
bool _minus = false;
template<typename T>
inline T sqr(T t) {
	return (t * t);
}
inline void read(ll &n) {
	n = 0;
	_minus = false;
	while (true) {
		ccc = getchar();
		if (ccc == ' ' || ccc == '\n')
			break;
		if (ccc == '-') {
			_minus = true;
			continue;
		}
		n = n * 10 + ccc - '0';
	}
	if (_minus)
		n *= -1;
}
inline bool read(int &n) {
	n = 0;
	_minus = false;
	while (true) {
		ccc = getchar();
		if (ccc == ' ' || ccc == '\n') {
			if (ccc == '\n')
				return true;
			break;
		}
		if (ccc == '-') {
			_minus = true;
			continue;
		}
		n = n * 10 + ccc - '0';
	}
	if (_minus)
		n *= -1;
	return false;
}
char wwww[19];
int kkkk;
inline void write(ll y) {
	long long x = y;
	kkkk = 0;
	if (x < 0) {
		putchar('-');
		x *= -1;
	}
	if (!x)
		++kkkk, wwww[kkkk] = '0';
	else
		while (x) {
			++kkkk;
			wwww[kkkk] = char(x % 10 + '0');
			x /= 10;
		}
	for (int i = kkkk; i >= 1; --i)
		putchar(wwww[i]);
}
#ifdef LOCAL
//#define DEBUG
#endif
#ifdef DEBUG
#define dbg if(1)
#else
#define dbg if(0)
#endif

const int MAX = 15;
int dp[1 << MAX];
int dp3[1 << MAX];
int dp2[1 << MAX][MAX];
int has[MAX][MAX];

inline void upd(int &a, int b) {
	a = max(a, b);
}

int max_val[MAX][1 << MAX];

bool con[1 << MAX];

int main() {
	sync;
	srand(time(NULL));
	cout.precision(10);
	cout << fixed;
#ifdef LOCAL
	input;
#else

#endif

	int n, m;
	cin >> n >> m;

	int sum = 0;

	for(int i = 0; i < n; i++) {
		con[1 << i] = true;
	}

	while(m--) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		has[a][b] = has[b][a] = c;
		con[(1 << a) | (1 << b)] = true;
		dp[(1 << a) | (1 << b)] = c;
		sum += c;
	}

	for(int i = 0; i < n; i++) {
		for(int mask = 0; mask < (1 << n); mask++) {
			if(mask & (1 << i)) {
				if(!con[mask ^ (1 << i)])
					continue;
				for(int a = 0; a < n; a++){
					if(mask & (1 << a)){
						if(a != i && has[a][i]){
							con[mask] = true;
						}
					}
				}
			}
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < (1 << n); j++) {
			if(j & (1 << i)) {
				dp[j] += dp[j ^ (1 << i)];
			}
		}
	}

	dp2[1][0] = 1;
	for(int mask = 0; mask < (1 << n); mask++) {
		for(int i = 0; i < n; i++) {
			if(dp2[mask][i]) {
				//cout << "$ " << mask << " " << i << " " << dp2[mask][i] << endl;
				for(int j = 0; j < n; j++) {
					if((mask & (1 << j)) == 0 && has[i][j]) {
						upd(dp2[mask | (1 << j)][j], dp2[mask][i] + has[i][j]);
					}
				}
			}
		}
	}

	for(int mask = 0; mask < (1 << n); mask++) {
		if((mask & 1) && (mask & (1 << (n - 1))) && dp2[mask][n - 1]) {
			dp3[mask] = dp2[mask][n - 1] - 1;
		}
	}

	for(int mask = 0; mask < (1 << n); mask++) {
		if(!dp3[mask])
		continue;
		int add = (1 << n) - 1;
		add ^= mask;
		for(int i = add; i; i = (i - 1) & add) {
			int res = 0;
			for(int j = 0; j < n; j++) {
				if((mask & (1 << j)) && con[i | (1 << j)]) {
					res = max(res, dp[i | (1 << j)]);
				}
			}
			if(res) {
				upd(dp3[mask | i], dp3[mask] + res);
			}
		}
	}

	cout << sum - dp3[(1 << n) - 1] << endl;

}


Measured memory_bytes: 2432