#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 20
#define M (1<<15)+10
#define lowbit(x) (x&(-x))
using namespace std;
int f[M][N],g[M][N],h[M],a[N][N],bit[M],n,m,tot,ans;
void upd(int &x,int y)
{
	if(y>x) x=y;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,d;scanf("%d%d%d",&x,&y,&d);
		tot+=d;
		a[x][y]=a[y][x]=d;
	}
	for(int i=1;i<=n;i++) bit[1<<(i-1)]=i;
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	int ss=1<<n;
	for(int i=1;i<ss;i++)
	{
		int j=bit[lowbit(i)];
		h[i]=h[i-lowbit(i)];
		for(int k=1;k<=n;k++) if(j!=k && (i&(1<<(k-1)))) h[i]+=a[j][k];
	}
	f[1][1]=0;
	for(int i=0;i<ss;i++)
		for(int j=1;j<=n;j++)
		{
			upd(g[i][j],f[i][j]);
			if(f[i][j]!=-1)
			{
				int t=ss-1-i;
				for(int k=t;k;k=(k-1)&t)
					upd(g[i+k][j],f[i][j]+h[k+(1<<(j-1))]);	
			}
			if(g[i][j]!=-1)
			{
				for(int k=1;k<=n;k++)
				{
					if((i&(1<<(k-1))) || a[j][k]==0) continue;
					upd(f[i+(1<<(k-1))][k],g[i][j]+a[j][k]);
				}
			}
		}
	ans=max(f[ss-1][n],g[ss-1][n]);
	printf("%d\n",tot-ans);
	return 0;
}