#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 13,M = (1 << 12) + 9,INF = 1e9;
int n,m;
int e[N][N];
bool valid[M][M];
int Log2[M];
int expand[M];//expand[i]：将状态i包含的节点全部扩展得到的状态
int min_dis[M][N];//min_dis[i][j]：从状态i打通到j所花费的最小代价 
int cost[M][M];//cost[i][j]：从状态i到j所花费的最小代价 
int dp[N][M];//dp[i][j]：扩展i层状态为j的最小代价

int lowbit(int x){
	return x & (-x);
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	int tot = (1 << n);//状态总数
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			e[i][j] = INF;
	
	
	for(int i = 1;i <= m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		u--;v--;
		if(u == v)
			continue;
		e[u][v] = min(e[u][v],w);
		e[v][u] = min(e[v][u],w);
	}
	
	//预处理Log2，方便快速确定lowbit对应的节点编号
	for(int i = 0;i < n;i++)
		Log2[1 << i] = i;
	
	//预处理expand,min_dis
	for(int i = 0;i < tot;i++)
		for(int j = 0;j < n;j++)
			min_dis[i][j] = INF;
	for(int i = 0;i < tot;i++){
		int tmp = i,Exp = i;
		while(tmp){
			int lb = lowbit(tmp);
			int u = Log2[lb];
			min_dis[tmp][u] = 0;
			for(int v = 0;v < n;v++)
				if(e[u][v] != INF){
					Exp |= (1 << v);
					min_dis[tmp][v] = min(min_dis[tmp][v],e[u][v]);
				}
			tmp -= lb;
		}
		expand[i] = Exp;
	}
	//预处理valid,cost
	for(int i = 0;i < tot;i++)
		for(int j = 0;j < tot;j++)
			cost[i][j] = INF;
	for(int i = 0;i < tot;i++)
		for(int j = 0;j < tot;j++){
			valid[i][j] = ((i & j) == i) && ((j & expand[i]) == j);
			if(valid[i][j]){
				cost[i][j] = 0;
				int diff = i ^ j;
				while(diff){
					int lb = lowbit(diff);
					int u = Log2[lb];
					cost[i][j] += min_dis[i][u];
					diff -= lb;
				}
			}
		}
	
	for(int i = 1;i <= n;i++)
		for(int j = 0;j < tot;j++)
			dp[i][j] = INF;
	for(int i = 0;i < n;i++)
		dp[1][1 << i] = 0;
	
	for(int i = 2;i <= n;i++)
		for(int j = 0;j < tot;j++)
			for(int k = 0;k < tot;k++)
				if(valid[k][j])
					dp[i][j] = min(dp[i][j],dp[i - 1][k] + (i - 1) * cost[k][j]);
	
	int ans = INF;
	for(int i = 1;i <= n;i++)
		ans = min(ans,dp[i][tot - 1]);
	cout << ans;
	return 0;
}