#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define U ((1<<n)-1)
using namespace std;

const int N = 16;
int a[N+2][N+2];
int cost[(1<<N)+2];
int dp[(1<<N)+2][N+2];
int n,m;

void update(int &x,int y) {x = max(x,y);}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		int x,y,z; scanf("%d%d%d",&x,&y,&z); x--; y--;
		a[x][y] = a[y][x] = z;
	}
	for(int i=0; i<=U; i++)
	{
		cost[i] = 0;
		for(int j=0; j<n; j++)
		{
			if((i&(1<<j))==0) continue;
			for(int k=j+1; k<n; k++)
			{
				if((i&(1<<k))==0) continue;
				cost[i] += a[j][k];
			}
		}
	}
	memset(dp,-1,sizeof(dp));
	dp[1][0] = 0;
	for(int i=1; i<=U; i+=2)
	{
		for(int j=0; j<n; j++)
		{
			if(dp[i][j]==-1) continue;
			if((i&(1<<j))==0) continue;
			for(int k=0; k<n; k++)
			{
				if(a[j][k]==0) continue;
				if(i&(1<<k)) continue;
				update(dp[i|(1<<k)][k],dp[i][j]+a[j][k]);
			}
			int c = (U-i)|(1<<j);
			for(int k=c; k>=0; k=(k==0 ? -1 : (k-1)&c))
			{
				update(dp[i|k][j],dp[i][j]+cost[k]);
			}
		}
	}
	int ans = 0;
	for(int i=(U>>1)+2; i<=U; i+=2) ans = max(ans,dp[i][n-1]);
	printf("%d\n",cost[U]-ans);
	return 0;
}