#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 15 + 5;
const int ALL = (1<<15) + 5;
const int inf = 0x3f3f3f3f;

inline void chk_max(int &a,int b){ if(a<b) a=b;}

int lb[ALL];
#define bit(x,i) (((x)>>(i))&1)
#define lowbit(x) ((x)&-(x))

int g[MAXN][MAXN];
int cost[ALL],f[ALL][MAXN];

int main(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; ++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=g[v][u]=w;
	}
	
	int all = (1<<n)-1;
	
	for(int mask=0; mask<=all; ++mask)
	{
		for(int i=1; i<=n; ++i) if(bit(mask,i-1))
			for(int j=1; j<i; ++j) if(bit(mask,j-1))
				cost[mask]+=g[i][j];
	}
	
	for(int mask=0; mask<=all; ++mask)
	{
		for(int i=1; i<=n; ++i) f[mask][i]=-inf;
		if(mask&1) f[mask][1]=cost[mask];
	}
	int ans=0;
	for(int mask=1; mask<=all; mask+=2)
	{
		if(bit(mask,n-1))
		{
			chk_max(ans,f[mask][n]);
			continue;
		}
		for(int i=1; i<=n; ++i) if(bit(mask,i-1))
		{
			if(f[mask][i]==-inf) continue;
			for(int mask2=all^mask; mask2; mask2=(mask2-1)&(all^mask))
			{
				for(int j=1; j<=n; ++j) if(bit(mask2,j-1))
					if(g[i][j]>0)
						chk_max(f[mask|mask2][j], f[mask][i]+g[i][j]+cost[mask2]);
			}
		}
	}
	
	printf("%d",cost[all]-ans);
	return 0;
}