#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
const int maxn = 15;

int n, m, f[1<<maxn][maxn], cost[1<<maxn], dis[maxn][maxn];

int calc(int s,int t){return cost[s|t]-cost[s]-cost[t];}
void upd(int &a,int b){a = (a < b ? a : b);}
int main()
{
	scanf("%d%d",&n,&m);
	fo(i,1,m)
	{
		int x, y, z; scanf("%d%d%d",&x,&y,&z);
		-- x; -- y; dis[x][y] = dis[y][x] = z;
	}
	fo(i,0,(1<<n)-1)
		fo(j,0,n-1) if(i&(1<<j))
			fo(k,j+1,n-1) if((i&(1<<k))&&dis[j][k])
				cost[i] += dis[j][k];
	memset(f,0x3f,sizeof(f));
	f[1][0] = 0;
	fo(s,0,(1<<n)-1) fo(i,0,n-1) if(f[s][i]!=0x3f3f3f3f&&(s&(1<<i)))
	{
		fo(j,0,n-1) if((!(s&(1<<j)))&&dis[i][j])
			upd(f[s|(1<<j)][j], f[s][i] + calc(s-(1<<i),(1<<j)));
		int t = (1<<n)-1-s;
		for(int y = t; y >= 1; y = ((y-1)&t))
			upd(f[s|y][i], f[s][i] + calc(s-(1<<i),y));
	}
	printf("%d\n",f[(1<<n)-1][n-1]);
	return 0;
}
