#include<bits/stdc++.h>
using namespace std;
#define MAXN (1<<15)+1
int n,m,a,b,c,sum[MAXN],f[MAXN][21],p[21][21],res,ans;
int main(){
	scanf("%d%d",&n,&m);
	int maxs=(1<<n)-1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		p[a][b]=p[b][a]=c;
		res+=c;
	}
	for(int s=0;s<=maxs;s++){
		for(int i=1;i<=n;i++)
		  if(s&(1<<(i-1))){
			for(int j=1;j<=n;j++)
			  if(s&(1<<(j-1))){
			  	sum[s]+=p[i][j];
			  }
		}
		sum[s]>>=1;
	}
	memset(f,-1,sizeof(f));
	f[1][1]=0;
	for(int s=0;s<=maxs;s++){
		for(int i=1;i<=n;i++){
			if(f[s][i]==-1) continue;
			for(int j=1;j<=n;j++){
				if(s&(1<<(j-1))) continue;
				if(!p[i][j]) continue;
				f[s|(1<<(j-1))][j]=max(f[s|(1<<(j-1))][j],f[s][i]+p[i][j]);
			}
			int rest=(maxs^s)|(1<<(i-1));
			for(int ss=rest;ss;ss=rest&(ss-1)){
				f[s|ss][i]=max(f[s|ss][i],f[s][i]+sum[ss]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=maxs;i++)
	  ans=max(ans,f[i][n]);
	printf("%d\n",res-ans);
}