#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define rep(i,x,y) for(LL i=x; i<=y; ++i)

using namespace std;
const int N=17,M=40000,INF=1000000000;
typedef long long LL;
LL n,m,ans,f[M],tot,dis[N][N],u,v,c;

LL getLL()
{
	char ch;
	LL f=1;
	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
	LL x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x*f;
}

LL query1(LL x)
{
	LL rt=0;
	rep(i,1,n)
		if(x&(1<<i-1))
			rep(j,i+1,n)
				if(x&(1<<j-1) && dis[i][j]!=INF)
					rt+=dis[i][j];
	return rt;
}

LL query2(LL x)
{
	LL rt=0,maxn=0;
	rep(j,1,n)
		if(x&(1<<j-1))
		{
			rt=0;
			rep(i,1,n)
				if(!(x&(1<<i-1)) && dis[j][i]!=INF)
					rt+=dis[j][i];
			maxn=max(maxn,rt);
		}
	return maxn;
}

int main()
{
	n=getLL(),m=getLL();
	rep(i,1,n) rep(j,1,n) dis[i][j]=INF;
	rep(i,1,m) u=getLL(),v=getLL(),dis[u][v]=dis[v][u]=c=getLL(),tot+=c;


	rep(i,1,(1<<n)-2)
		if(i==1 || f[i])
		{
			rep(j,1,n)
				if(!(i&(1<<j-1)))
				{
					LL maxn=0;
					rep(k,1,n)
						if(i&(1<<k-1) && dis[j][k]<INF)
							maxn=max(maxn,dis[j][k]);
					if(maxn) f[i|(1<<j-1)]=max(f[i|(1<<j-1)],f[i]+maxn);
				}
		}


	rep(i,1,(1<<n)-1)
		if(i&1 && i&(1<<n-1) && f[i])
			ans=max(ans,f[i]+query1(((1<<n)-1)^i)+query2(i));
	printf("%lld\n",tot-ans);
	return 0;
}