#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define eps 1e-10
#define inf 1e9
#define For(i,j,k)	for(int i=j;i<=k;++i)
#define Dow(i,j,k)	for(int i=k;i>=j;--i)
#define ll long long
using namespace std;
inline ll read()
{
	ll t=0,f=1;char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	t=t*10+c-48,c=getchar();
	return t*f;
}
const int N=(1<<20);
int n,m,e[30][30],in[N],to[N][30],dp[N][30];
int x,y,z;
int main()
{
	n=read();m=read();
	For(i,1,m)
	{
		x=read();y=read();z=read();
		e[x][y]=e[y][x]=z;
	}
	int mx=(1<<(n+1))-1;
	For(i,1,mx)
		For(j,1,n)
			if((i&(1<<j)))	For(k,j+1,n)	if((i&(1<<k)))	in[i]+=e[j][k];
	For(i,1,mx)
		For(j,1,n)
		{
			For(k,1,n)
				if(i&(1<<k))	
					to[i][j]+=e[j][k];
		}
	For(i,0,mx)	For(j,0,n)	dp[i][j]=-1;
	dp[2][1]=0;
	For(i,2,mx)
		For(j,1,n)// dp[i][j] to update
			if(dp[i][j]>=0)
				if(i&(1<<j))
				{
					For(k,1,n)
						if(i&(1<<k))	continue;
						else
							if(e[j][k])	dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+e[j][k]);
					int Cu=mx-i;
					for(int tmp=mx-i;tmp;tmp=(tmp-1)&Cu)
					{
						dp[i|tmp][j]=max(dp[i|tmp][j],dp[i][j]+to[tmp][j]+in[tmp]);
					}
				}
	printf("%d\n",in[mx]-dp[mx][n]);
}