#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define LL long lone
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
struct stane{int a,b;LL c;};
int n,m,N,g[20][20],val[40010],dp[40010][20];
vector<pii>vv;
vector<int>vc;
inline void update(int &a,int b){ if(a<b) a=b;}
int solve(){
	memset(g,0,sizeof g);
	memset(val,0,sizeof val);
	int i,j,k,r,rest,u,v,w;
	int sum=0;
	N=(1<<n);
	for(i=1;i<=m;i++){
		u=vv[i-1].F;
		v=vv[i-1].S;
		w=vc[i-1];
		g[u][v]=g[v][u]=w;
		sum+=w;
	}
	memset(dp,-1,sizeof dp);
	for(i=1;i<N;i++){
		for(j=0;j<n;j++)if(i&(1<<j))break;
		val[i]=val[i^(1<<j)];
		for(k=j+1;k<n;k++)if(i&(1<<k))val[i]+=g[j][k];
		if(j==0)dp[i][0]=val[i];
	}
	for(i=1;i<N;i++)
		for(j=0;j<n;j++){
			if((v=dp[i][j])<0)continue;
			for(k=0;k<n;k++){
				if(i&(1<<k))continue;
				if(g[j][k]==0)continue;
				update(dp[i^(1<<k)][k],v+g[j][k]);
				for(rest=r=(N-1)^i^(1<<k);r;r=(r-1)&rest)
					update(dp[i^r^(1<<k)][k],v+val[r^(1<<k)]+g[j][k]);
			}
		}
	return sum-dp[N-1][n-1];
	return 0;
}
vector<stane>road;
LL cost[1<<16];
LL dp2[1<<16][16];
LL lis[16][16];
LL ddp[1<<16];
LL mt[1<<16][16];
int main(){
	cin>>n>>m;
	if(n==1)return 1;
	LL S=0;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		vv.pb(make_pair(a,b));
		vc.pb(c);
		road.pb({a,b,c});
		S+=c;
		if(lis[a][b])return 1;
		lis[a][b]=max(lis[a][b],(LL)c);
		lis[b][a]=max(lis[b][a],(LL)c);
	}
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if((i>>j)&1)continue;
			for(int k=0;k<n;k++)
				if((i>>k)&1)
					mt[i][j]=max(mt[i][j],lis[k][j]);
		}
	}
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<road.size();j++)
			if((i>>road[j].a)&1)
				if ((i>>road[j].b)&1)
					cost[i]+=road[j].c;
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			dp2[i][j]=LLONG_MIN;
	dp2[1][0]=0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(!(i>>j)&1)continue;
			if(dp2[i][j]!=LLONG_MIN)for(int k=0;k<n;k++){
				if((i>>k)&1)continue;
				if(lis[j][k])
					dp2[i|(1<<k)][k]=max((LL)dp2[i|(1<<k)][k],dp2[i][j]+lis[j][k]);
			}
		}
	}
	for(int i=0;i<(1<<n);i++)ddp[i]=dp2[i][n-1];
	for(int i=0;i<(1<<n);i++){
		if(ddp[i]!=LLONG_MIN){
			if((!(i>>0)&1)||(!(i>>(n-1)&1)))return 1;
			for(int j=i;j<(1<<n);j++,j|=i){
				if(i==j)continue;
				int xr=(j^i);
				if(xr&i)return 1;
				if(xr==0)return 1;
				LL cosm=max(cost[1|xr],cost[(1<<(n-1))|xr]);
				for(int ii=0;ii<n;ii++)if((i>>ii)&1)
					cosm=max(cosm,cost[1<<(ii)|xr]);
				ddp[j]=max(ddp[j],ddp[i]+cosm);
			}
		}
	}
	cout<<S-ddp[(1<<n)-1]<<endl;
	return 0;
}
