#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = (1 << 12), M = 13;
int n, m, ds[M][M], dis[M][N], dp[632000][M];
int poow(int a, int b) {
	int as = 1;
	while(b) {
		if(b & 1) as *= a;
		a *= a, b >>= 1;
	}
	return as;
}
int gt(int x) {
//	cout << x << " ";
	int nw = 0;
	while(x) {
		nw += poow(3, __lg(x & -x));
		x -= (x & -x);
	}
//	cout << nw << "\n";
	return nw;
}
signed main() {
    // cout << gt(8);
//	cout << poow(3, 2);
	cin >> n >> m;
	if(n == 1) {
		cout << 0;
		return 0;
	}
	memset(ds, 0x3f, sizeof ds);
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ds[u][v] = ds[v][u] = min(ds[u][v], w);
	}
	memset(dis, 0x3f, sizeof dis);
	for(int j = 1; j <= n; j++) {
		for(int i = 0; i < (1 << n); i++) {
			int mn = 0x3f3f3f3f;
			for(int k = 0; k < n; k++) {
				if(!((i >> k) & 1)) continue;
				mn = min(mn, ds[j][k + 1]);
			}
			dis[j][i] = mn;
//			cout << j << " " << i << " " << dis[j][i] << "\n";
		}
	}
	memset(dp, 0x3f, sizeof dp);
	dp[2][1] = 0;
	for(int i = 1; i < (1 << n); i++) {
//		cout << i << "\n";
		for(int j = i; j; j = (j - 1) & i) {
			int ti = gt(i), tj = gt(j);
			for(int k = 1; k <= n; k++) {
//				cout << i << " " << j << " " <<  k << " " << dp[ti + tj][k] << "\n";
				for(int u = 1; u <= n; u++) {
					if((i >> u - 1) & 1) continue;
					dp[ti + tj + 2 * poow(3, u - 1)][k] = min(dp[ti + tj + 2 * poow(3, u - 1)][k], dp[ti + tj][k] + dis[u][i ^ j] * ((k == 1 ? 0x3f3f3f3f : k) - 1));
					dp[ti + 2 * poow(3, u - 1)][k + 1] = min(dp[ti + 2 * poow(3, u - 1)][k + 1], dp[ti + tj][k] + dis[u][j] * k);
//					cout << ti + 2 * poow(3, u - 1) << "\n";
//					cout << u << " " << j << " " << dis[u][j] << " " << (int)dp[ti + 2 * poow(3, u - 1)][k] << "\n";
				}
			}
		}
//		cout << "\n";
	}
	int ans = 0x3f3f3f3f;
	for(int i = 0; i < (1 << n); i++) {
		int ti = gt(i), tj = gt((1 << n) - 1);
		for(int k = 2; k <= n; k++) ans = min(ans, dp[ti + tj][k]);
	}
	cout << ans;
	return 0;
}