#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<fstream>
#include<map>
#include<queue>
#include<stack>
using namespace std;
long long n,m,sum,c[20][20];
long long f[1<<15][15],p[1<<15];
int main(){
	memset(f,-1,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		sum+=w;
		c[u][v]=w,c[v][u]=w;
	}
	for(int i=0;i<=(1<<n)-1;i++){
		for(int j=0;j<=n-1;j++){
			if(i&(1<<j)){
				for(int k=j+1;k<=n-1;k++){
					if(i&(1<<k)){
						p[i]=p[i]+c[j][k];
					}
				}
			}
		}
	}
	f[1][0]=0;
	for(int i=0;i<=(1<<n)-1;i++){
		for(int j=0;j<=n-1;j++){
			if(f[i][j]==-1){
				continue;
			}
			int x=(((1<<n)-1)^i)|(1<<j);
			for(int k=x;k;k=(k-1)&x){
				f[i|k][j]=max(f[i|k][j],f[i][j]+p[k]);
			}
			for(int k=1;k<=n-1;k++){
				if((!(i&(1<<k)))&&c[j][k]){
					f[i|(1<<k)][k]=max(f[i|(1<<k)][k],f[i][j]+c[j][k]);
				}
			}
		}
	}
	long long ans=100000000000000;
	for(int i=0;i<=(1<<n)-1;i++){
		for(int j=0;j<=n-1;j++){
			if(i&(1<<j)){
				ans=min(ans,sum-f[i][n-1]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}