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

int n,m,N,f[15][1<<15],s[1<<15],e[15][15],ans;

void upd(int &x,int y){if (x<y)  x=y;}

void work()
{
	scanf("%d %d",&n,&m),N=1<<n;
	for (int i=1,u,v,w; i<=m; i++)
		scanf("%d %d %d",&u,&v,&w),u--,v--,e[u][v]=e[v][u]=w;
	for (int i=1; i<N; i++)
		for (int j=0; j<n; j++)
			for (int k=j; k<n; k++)
				if ((i&(1<<j))&&(i&(1<<k)))
					s[i]+=e[j][k];
	memset(f,128,sizeof(f));
	f[0][1]=0;
	for (int i=1; i<N; i+=2)
		for (int j=0; j<n; j++)
			if (i&(1<<j))
				{
					int x=N-1-i;
					for (int k=x; k; k-=x&-x,k&=x)
						upd(f[j][i|k],f[j][i]+s[k|(1<<j)]);
					for (int k=0; k<n; k++)
						if ((x&(1<<k))&&(e[j][k]))
							upd(f[k][i|(1<<k)],f[j][i]+e[j][k]);
					if (j==n-1)  upd(ans,f[j][i]);
				}
	printf("%d",s[N-1]-ans);
}

int main()
{
	work();
	return 0;
}
