#include<bits/stdc++.h>
using namespace std;
const int N=15;
int d[N][N],dp[1<<N][N],a[1<<N],n,m,ans,sum;
void chmax(int &a,int b){if(a==-1||a<b)a=b;}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u--;
		v--;
		d[u][v]=d[v][u]=w;
		sum+=w;
	}
	memset(dp,-1,sizeof(dp));
	for(int s=0;s<(1<<n);s++)
		for(int i=0;i<n;i++)
			if(s&(1<<i))
				for(int j=i+1;j<n;j++)
					if(s&(1<<j))
						a[s]+=d[i][j];
	dp[1][0]=0;
	for(int s=1;s<(1<<n);s++)
	{
		for(int i=0;i<n;i++)
		{
			if(dp[s][i]==-1)
				continue;
			for(int j=0;j<n;j++)
			{
				if(s&(1<<j))
					continue;
				if(!d[i][j])
					continue;
				chmax(dp[s|(1<<j)][j],dp[s][i]+d[i][j]);
			}
			int k=(((1<<n)-1)^s)|(1<<i);
			for(int t=k;t;t=(t-1)&k)
				chmax(dp[s|t][i],dp[s][i]+a[t]);
		}
	}
	for(int s=0;s<(1<<n);s++)
		ans=max(ans,dp[s][n-1]);
	printf("%d\n",sum-ans);
	return 0;
}