#include <iostream>
#include <cstring>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 13, MAXS = 1 << 13, INF = 0x3f3f3f3f;
// D[s][t]：已选点集为s，下一层要加入的点集为t时，
// 新加入的所有点与原有点之间的最小边权和。
int D[MAXS][MAXS];
// f[h][s]：已选点集为s、【当前】树高度为h时的最小花费
int f[N][MAXS];
int a[N][N]; // 邻接矩阵
int Log2[MAXS] = {-1, 0};
int okstat[MAXS], tot; // 暂存需要枚举的子集

int main() {
	int n, m;
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = 500005;
	
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> w;
		// 注意处理重边
		a[u][v] = a[v][u] = min(w, a[u][v]);
	}
	
	for (int i = 2; i < MAXS; i++) Log2[i] = Log2[i >> 1] + 1;
	
	int U = (1 << n) - 1;
	for (int i = 1; i <= U; i++) {
		int sup = U ^ i;
		// 如果直接枚举sup的子集，顺序就是从大到小的，
		// 不符合DP的顺序，所以要暂存从小到大的子集枚举顺序，
		// 然后逆序（从小到大）处理
		tot = 0;
		for (int j = sup; j; j = (j - 1) & sup) okstat[++tot] = j;
		for (int j = tot; j; j--) {
			int s = okstat[j];
			int v = Log2[lowbit(s)] + 1;
			int minn = INF;
			for (int i1 = i; i1; i1 -= lowbit(i1)) {
				int u = Log2[lowbit(i1)] + 1;
				minn = min(minn, a[u][v]);
			}
			D[i][s] = D[i][s ^ lowbit(s)] + minn;
		}
	}
	
	memset(f, 0x3f, sizeof f);
	for (int i = 0; i <= n; i++) f[0][1 << i] = 0;
	// 认真读题！！！你要打通的道路 (u, v) 的代价中，
	// K 就是 v 的深度（根节点深度为 1）！！！
	for (int i = 1; i < n; i++) // 根节点也要选，所以从1开始
		for (int s = 1; s <= U; s++)
			for (int t = s; t; t = (t - 1) & s)
				f[i][s] = min(f[i][s], f[i - 1][s ^ t] + i * D[s ^ t][t]);
	
	int ans = 0x7fffffff;
	for (int i = 0; i <= n; i++) ans = min(ans, f[i][U]);
	cout << ans;
	
	return 0;
}