#include<cstdio>
#include<algorithm>
using namespace std;
#define N 17
int v[N][N],n,m,a,b,c,as;
int dp[67890][N],su[67890],s1;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&a,&b,&c),v[a][b]=v[b][a]=c,s1+=c;
	for(int i=1;i<1<<n;i++)
	for(int j=1;j<=n;j++)
	for(int k=j+1;k<=n;k++)
	if((i&(1<<j-1))&&(i&(1<<k-1)))su[i]+=v[j][k];
	for(int i=0;i<1<<n;i++)for(int j=1;j<=n;j++)dp[i][j]=-1e9;
	for(int i=1;i<1<<n;i+=2)dp[i][1]=su[i];
	for(int i=1;i<1<<n;i++)
	for(int j=1;j<=n;j++)
	if(i&(1<<j-1))
	for(int k=((1<<n)-1)^i;k;k=(k-1)&(((1<<n)-1)^i))
	for(int l=1;l<=n;l++)
	if(k&(1<<l-1))
	if(v[j][l])
	dp[i|k][l]=max(dp[i|k][l],dp[i][j]+su[k]+v[j][l]);
	int as=0;
	for(int i=1;i<1<<n;i++)as=max(as,dp[i][n]);
	printf("%d\n",s1-as);
}