#include<bits/stdc++.h>
#define ll long long
using namespace std;
int ha,n,m,i,j,x,y,w,k,mx,ans,sz[100010],f[50001][16],a[101][101];
int main(){
	scanf("%d%d",&n,&m);
	memset(f,-1,sizeof(f));
	f[1][0]=0;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		x--;y--;
		a[x][y]=a[y][x]=w;
		ans+=w;
	}
	mx=1<<n;
	for(i=0;i<mx;i++){
		for(j=0;j<n;j++)if(i&(1<<j))
		 for(k=j+1;k<n;k++)if(i&(1<<k))sz[i]+=a[j][k];
	}
	for(i=1;i<mx-1;i++)
	 for(j=0;j<n;j++)if(f[i][j]!=-1){
	 //	printf("%d %d %d\n",i,j,f[i][j]);
	 	for(k=0;k<n;k++)if((!(i&(1<<k)))&&a[j][k])f[i|1<<k][k]=max(f[i|1<<k][k],f[i][j]+a[j][k]);
	 	for(k=(mx-1)^i;k;k=(k-1)&((mx-1)^i))if(!(k&(1<<n-1)))f[i|k][j]=max(f[i|k][j],f[i][j]+sz[k|1<<j]);
	 }
	//printf("%d\n",mx);
	for(i=1;i<mx;i++){
	  ha=max(ha,f[i][n-1]);
	  //printf("%d %d %d\n",i,n-1,f[i][n-1]);
}
	printf("%d",ans-ha);
}
/*
一道挺好想的dp，
最后的路径一定是一条从s到t的链和在链上的点向外挂出去的一些联通分量。
那么就可以dp表示到了i与s联通的集合为j 
*/