#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
void read(int &x){
	char ch;bool ok;
	for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;
	for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;
}
#define rg register
const int maxn=1<<16;
int n,m,v[20][20];
long long ans,in[maxn],f[maxn][20];
vector<int>d[20];
int main(){
	read(n),read(m);
	for(rg int i=1,x,y,z;i<=m;i++){
		read(x),read(y),read(z),v[x][y]=v[y][x]=z;
		ans+=z;
		d[x].push_back(y),d[y].push_back(x);
	}
	int tot=1<<n;
	for(rg int i=0;i<tot;i++){
	    if(in[i])continue;
		for(rg int j=1;j<=n;j++)
			if(!(i&(1<<(j-1)))){
				int w=d[j].size(),sum=in[i];
				for(rg int k=0;k<w;k++)
					if(i&(1<<(d[j][k]-1)))sum+=v[j][d[j][k]];
				in[i|(1<<(j-1))]=sum;
		}
	}
	memset(f,-1,sizeof f);
	f[1][1]=0;
	for(rg int i=0;i<tot;i++)
		for(rg int k=1;k<=n;k++){
			if(f[i][k]==-1)continue;
			if(i&(1<<(k-1))){
				for(rg int j=1;j<=n;j++)
					if(!(i&(1<<(j-1)))&&v[k][j])
						f[i|(1<<(j-1))][j]=max(f[i][k]+v[k][j],f[i|(1<<(j-1))][j]);
				int now=((tot-1)^i)|(1<<(k-1));
				for(rg int j=now;j;j=(j-1)&now)
				    if(j&(1<<(k-1)))f[i|j][k]=max(f[i][k]+in[j],f[i|j][k]);
			}
		}
	printf("%lld\n",ans-f[tot-1][n]);
}
