#include<bits/stdc++.h>
using namespace std;

const int MAXN = 17, MAXS = 32775;

class solver{
	
public:
	int n, m, N, g[MAXN][MAXN], val[MAXS], dp[MAXS][MAXN];
	vector<pair<int, int> > vv;
	vector<int> vc;
	inline void update(int &a, int b){ if (a < b) a = b; }
	int main(){
		memset(g, 0, sizeof(g));
		memset(dp, 0, sizeof(dp));
		memset(val, 0, sizeof(val));
		int i, j, k, r, rest, u, v, w, sum = 0;
		N = 1 << n;
		for (i = 1; i <= m; ++i){
			u = vv[i - 1].first;
			v = vv[i - 1].second;
			w = vc[i - 1];
			g[u][v] = g[v][u] = w;
			sum += w;
		} memset(dp, -1, sizeof(dp));
		for (i = 1; i < N; ++i){
			for (j = 0; j < n; ++j)
				if (i & (1 << j)) break;
			val[i] = val[i ^ (1 << j)];
			for (k = j + 1; k < n; ++k)
				if (i & (1 << k))
					val[i] += g[j][k];
			if (j == 0) dp[i][0] = val[i];
		}
		for (i = 1; i < N; ++i)
			for (j = 0; j < n; ++j){
			if ((v = dp[i][j]) < 0) continue;
			for (k = 0; k < n; ++k){
				if (i & (1 << k)) continue;
				if (g[j][k] == 0) continue;
				update(dp[i ^ (1 << k)][k], v + g[j][k]);
				for (rest = r = (N - 1) ^ i ^ (1 << k); r; r = (r - 1) & rest)
					update(dp[i ^ r ^ (1 << k)][k], v + val[r ^ (1 << k)] + g[j][k]);
			}
			}
		return sum - dp[N - 1][n - 1] ;
		return 0;
	}
};

solver sol;

int n;
int m;

struct st{
	int a;
	int b;
	long long int c;
};
vector<st> road;

long long int cost[1 << 16];

long long int dp[1 << 16][16];
long long int lis[16][16];
long long int ddp[1 << 16];
long long int mt[1 << 16][16];
int main(){
	cin >> n >> m;
	sol.n = n;
	sol.m = m;
	if (n == 1)return 1;
	long long int S = 0;
	for (int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a--; b--;
		sol.vv.push_back(make_pair(a, b));
		sol.vc.push_back(c);
		road.push_back({ a, b, c });
		S += c;
		if (lis[a][b])return 1;
		lis[a][b] = max(lis[a][b], (long long int)c);
		lis[b][a] = max(lis[b][a], (long long int)c);
	}
	for (int i = 0; i < (1 << n); i++){
		for (int j = 0; j < n; j++){
			if ((i >> j) & 1)continue;
			for (int k = 0; k < n; k++){
				if ((i >> k) & 1){
					mt[i][j] = max(mt[i][j], lis[k][j]);
				}
			}
		}
	}
	for (int i = 0; i < (1 << n); i++){
		for (int j = 0; j < road.size(); j++){
			if ((i >> road[j].a) & 1){
				if ((i >> road[j].b) & 1){
					cost[i] += road[j].c;
				}
			}
		}
	}
	for (int i = 0; i < (1 << n); i++){
		for (int j = 0; j < n; j++){
			dp[i][j] = LLONG_MIN;
		}
	}
	dp[1][0] = 0;
	for (int i = 0; i < (1 << n); i++){
		for (int j = 0; j < n; j++){
			if (!(i >> j) & 1){
				continue;
			}
			if (dp[i][j] != LLONG_MIN){
				for (int k = 0; k < n; k++){
					if ((i >> k) & 1)continue;
					if (lis[j][k]){
						dp[i | (1 << k)][k] = max(dp[i | (1 << k)][k], dp[i][j] + lis[j][k]);
					}
				}
			}
		}
	}
	for (int i = 0; i < (1 << n); i++){
		ddp[i] = dp[i][n - 1];
	}
	for (int i = 0; i < (1 << n); i++){
		if (ddp[i] != LLONG_MIN){
			if ((!(i >> 0) & 1)||(!(i>>(n-1)&1))){
				return 1;
			}
			for (int j = i; j < (1 << n); j++, j |= i){
				if (i == j)continue;
				int xr = (j^i);  //adding
				if (xr&i)return 1;
				if (xr==0)return 1;
				long long int cosm = max(cost[1 | xr], cost[(1 << (n - 1)) | xr]);
				for (int ii = 0; ii < n; ii++){
					if ((i >> ii) & 1){
						cosm = max(cosm, cost[1<<(ii)|xr]);
					}
				}
				ddp[j] = max(ddp[j], ddp[i] + cosm);
			}
		}
	}
	//int s = sol.main();
	/*if (s < S - ddp[(1 << n) - 1]){
		return 1;
	}*/
	printf("%lld\n", S - ddp[(1 << n) - 1]);
	return 0;
}

Measured memory_bytes: 14592