#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define MAXN 15
#define INF 0x3F3F3F3F
int v[MAXN][MAXN], n, m, x, y, z;
int c[1 << MAXN][MAXN], f[1 << MAXN][MAXN];
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0;i < m;i++){
		scanf("%d%d%d", &x, &y, &z);
		x--;y--;
		v[x][y] = v[y][x] = z;
	}
	for(int d = 0;d < (1 << n);d++){
		for(int i = 0;i < n;i++){
			f[d][i] = INF;
			for(int j = 0;j < n;j++)if((d >> j) & 1)c[d][i] += v[i][j];
		}
	}
	f[1][0] = 0;
	for(int d = 0;d < (1 << n);d++){
		for(int i = 0;i < n;i++){
			if(((d >> i) & 1) && f[d][i] != INF){
				for(int j = 0;j < n;j++){
					if(!((d >> j) & 1) && v[i][j]){
						f[d | (1 << j)][j] = std::min(
							f[d | (1 << j)][j],
							f[d][i] + c[d][j] - v[i][j]
						);
					}
				}
				register int next = d ^ (1 << i), st = ((1 << n) - 1) ^ d, sum;
				for(int j = st;j > 0;j = (j - 1) & st){
					sum = 0;
					for(int l = 0;l < n;l++)if((j >> l) & 1)sum += c[next][l];
					f[d | j][i] = std::min(f[d | j][i], f[d][i] + sum);
				}
			}
		}
	}
	printf("%d\n", f[(1 << n) - 1][n - 1]);
	return 0;
}