#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define re register
const int N = 14, S = (1<<12) + 2;
int n, m;
int g[N][N];

int dp[N][S], cost[S][S];	//dp[i][s]：树高（距起点）为i，当前点集为S的生成树的最小代价
signed main() {
	memset(g, 0x3f, sizeof(g));
	scanf("%d%d", &n, &m);
	for(re int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = g[v][u] = std::min(w, g[u][v]);
	}
	
	for(re int s = 0; s < 1 << n; ++s)
		for(re int s0 = s; ; s0 = s0-1 & s) {	//枚举s的子集，预处理从s0加边到s的
			re int t = s ^ s0;	//t为s0关于s的补集，即s-s0
			for(re int i = 1; i <= n; ++i) 
				if(t & 1 << i-1) {
					re int mn = inf;
					for(re int j = 1; j <= n; ++j)
						if(s0 & 1 << j-1) mn = std::min(mn, g[j][i]);
					if(mn == inf) {cost[s0][s] = inf; break;}	//无法转移
					cost[s0][s] += mn;	//转移成功一个点，加上代价
				}
			if(s0 == 0) break;
		}
	
	memset(dp, 0x3f, sizeof(dp));
	for(re int i = 1; i <= n; ++i) dp[i][1 << i-1] = 0;	//边界：加起点，状态值为0
	for(re int i = 2; i <= n; ++i)
		for(re int s = 0; s < 1 << n; ++s)	//枚举点集
			for(re int s0 = s; ; s0 = s0-1 & s) {	//枚举s的子集
				if(cost[s0][s] != inf) dp[i][s] = std::min(dp[i][s], dp[i-1][s0] + (i-1)*cost[s0][s]);
				if(s0 == 0) break;
			}
	
	int ans = inf;
	for(re int i = 1; i <= n; ++i) ans = std::min(ans, dp[i][(1<<n) - 1]);	//枚举所有可能的树高
	printf("%d", ans);
    return 0;
}