#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
using namespace std;
typedef long long LL;
const int N=16;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,m,tot,dp[N][1<<N],ans;
int c[N],w[N][1<<N],can[1<<N];
int q[1<<N],cnt;
int main()
{
	int x,y,z;
	read(n),read(m);
	For(i,1,m)
	{
		read(x),read(y),read(z);
		c[x]|=(1<<(y-1)),w[x][1<<(y-1)]=z;
		c[y]|=(1<<(x-1)),w[y][1<<(x-1)]=z;
		ans+=z;
	}
	For(i,1,n)
	{
		cnt=0;
		for(int x=c[i];x;x=(x-1)&c[i])
			q[++cnt]=x;
		rFor(j,cnt,1)
		{
			int x=q[j];
			w[i][x]=w[i][x^lowbit(x)]+w[i][lowbit(x)];
		}
	}
	mem(dp,-inf);
	dp[1][1]=0;
	tot=(1<<n)-1;
	For(x,1,tot)
	{
		For(u,1,n)
			if(x&(1<<(u-1)))
				can[x]+=w[u][x&c[u]];
		can[x]>>=1;
	}
	For(x,1,tot)
		For(u,1,n)
		if(dp[u][x]>=0){
			int bx=tot^x;
			for(int sm=bx;sm;sm=(sm-1)&bx)
				chkmax(dp[u][x|sm],dp[u][x]+can[sm|(1<<(u-1))]);
			For(v,1,n)
				if(c[u]&(1<<(v-1))&&!(x&(1<<(v-1))))
					chkmax(dp[v][x|(1<<(v-1))],dp[u][x]+w[v][1<<(u-1)]);
		}
	printf("%d\n",ans-dp[n][tot]);
	return 0;
}
