#include<bits/stdc++.h>
#define ll long long
#define N 20
#define inf 1e9
#define rep(i,j,k) for(ll i=j;i<=k;++i)
using namespace std;
inline ll read(){
    ll x=0,f=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
    return f?-x:x;
}
ll n,m,G[N][N],f[1<<N][N],s[1<<N],sum;
int main(){
    n=read();m=read();
    rep(i,1,m){
		ll x=read()-1,y=read()-1;
		G[x][y]=G[y][x]=read(); sum+=G[x][y];
	}
    rep(i,0,1<<n) rep(j,0,n) if((i>>j)&1)
		rep(k,j+1,n) if((i>>k)&1) s[i]+=G[j][k];
    rep(i,0,1<<n) rep(j,0,n) f[i][j]=-inf;
    rep(i,0,1<<n) if(i&1) f[i][0]=s[i];
    rep(i,0,1<<n) rep(j,0,n) if((i>>j)&1)
		for(ll k=i;k;k=(k-1)&i) if(k&1)
			rep(l,0,n) if(((k>>l)&1)&&((~k>>j)&1)&&G[l][j])
				f[i][j]=max(f[i][j],f[k][l]+G[l][j]+s[i^k]);
    printf("%d\n",sum-f[(1<<n)-1][n-1]);
    return 0;
}
%:pragma GCC optimize "-O3"
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("fast-math")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC target("sse3","sse2","sse")
#include<bits/stdc++.h>
#define ll long long
#define heap priority_queue
using namespace std;
const ll maxn=15+1;
const ll inf=9e17;
ll ans,sum,dp[maxn][1<<maxn],dis[1<<maxn],g[maxn][maxn],tmp,lim,n,m;
inline ll lowbit(ll x){
	return x&-x;
}
int main()
{
	cin>>n>>m;
	ll u,v,w;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		--u;
		--v;
		g[u][v]=g[v][u]=w;
		sum+=w;
	}
	lim=(1<<n)-1;
	for(int i=1;i<=lim;i++)
	{
		tmp=log2(lowbit(i));
		dis[i]=dis[i^(1<<tmp)];
		for(int j=0;j<n;j++)
			if(g[tmp][j]&&(i&(1<<j)))
				dis[i]+=g[tmp][j];
	}
	memset(dp,0xc0,sizeof(dp));
	dp[0][1]=0;
	ans=-inf;
	for(int i=1;i<=lim;i++)
	{
		if(!(i&1))
			continue;
		for(int j=0;j<n;j++)
			if(i&(1<<j))
			{
				for(int k=i;k;k=(k-1)&i)
					if(k&(1<<j))
						dp[j][i]=max(dp[j][i],dp[j][i^k^(1<<j)]+dis[k]);
				for(int k=lim^i;k;k-=lowbit(k))
				{
					tmp=log2(lowbit(k));
					if(g[tmp][j]) 
						dp[tmp][i^(1<<tmp)]=max(dp[tmp][i^(1<<tmp)],dp[j][i]+g[tmp][j]);
				}
			}
		if(i&(1<<(n-1)))
			ans=max(ans,dp[n-1][i]);
	}
	cout<<sum-ans<<"\n";
	return 0;
}