#include<bits/stdc++.h>
using namespace std;
const int Max_N=15,Max_S=1<<15;
int N,M,Sum=0,A[Max_N+5][Max_N+5]={},f[Max_S+5][Max_N+5]={},P[Max_S+5]={};
int main(){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		int x,y,v; 
		scanf("%d%d%d",&x,&y,&v);
		Sum+=v; A[x][y]=A[y][x]=v;
	}
	for(int i=0;i<1<<N;i++){
		for(int j=1;j<=N;j++)
		 if((1<<(j-1))&i){
		 	for(int k=j+1;k<=N;k++)
		 	 if((1<<(k-1))&i)
		 	  P[i]+=A[j][k];
		 }
	}
	for(int i=1;i<=N;i++)
	 for(int j=0;j<1<<N;j++)
	  f[j][i]=-(1<<30);
	f[1][1]=0;
	for(int i=0;i<1<<N;i++){
		for(int j=1;j<=N;j++){
			if((1<<(j-1))&i)
			for(int k=1;k<=N;k++)
			 if(((1<<(k-1))&i)&&k!=j&&A[j][k]>0)
			  f[i][j]=max(f[i][j],f[i^(1<<(j-1))][k]+A[j][k]);
			for(int k=i;k;k=(k-1)&i)
			 if(k&(1<<(j-1)))
			  f[i][j]=max(f[i][j],f[(i^k)|(1<<(j-1))][j]+P[k]);
		}
	}
	printf("%d\n",Sum-f[(1<<N)-1][N]);
	return 0;
}