#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<15)+5;
int n,m;
int dp[maxn][16];
int mp[16][16],val[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		mp[v][u]=mp[u][v]=w;
	}
	memset(dp,-1,sizeof(dp));
	int all=(1<<n)-1;
	dp[1][1]=0;
	for(int s=0;s<=all;s++)
	{
		for(int i=1;i<=n;i++)
		if(s&(1<<i-1))
		{
			for(int j=i+1;j<=n;j++)
			if(s&(1<<j-1))val[s]+=mp[i][j];
		}
		for(int i=1;i<=n;i++)
		if(s&(1<<i-1))
		{
			for(int s0=s;s0;s0=(s0-1)&s)if(((s^s0)&(1<<i-1))&&dp[s^s0][i]!=-1)dp[s][i]=max(dp[s^s0][i]+val[s0|(1<<i-1)],dp[s][i]);
			for(int j=1;j<=n;j++)if((s&(1<<j-1))&&j!=i&&mp[j][i]&&dp[s^(1<<i-1)][j]!=-1)dp[s][i]=max(dp[s][i],dp[s^(1<<i-1)][j]+mp[j][i]);	
		}
	}
	printf("%d\n",val[all]-dp[all][n]);
}