#include<bits/stdc++.h>
using namespace std;
int n,m,g[15][15],dp[1<<15][15],cost[1<<15],sum;
int main() {
	memset(dp,-1,sizeof(dp));
	memset(g,-1,sizeof(g));
	scanf("%d%d",&n,&m);
	while(m--) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a-1][b-1]=g[b-1][a-1]=c;
		sum+=c;
	}
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			if((1<<j)&i)
				for(int k=j+1;k<n;k++)
					if((1<<k)&i&&g[j][k]>-1)
						cost[i]+=g[j][k];
	for(int i=1;i<1<<n;i+=2) dp[i][0]=cost[i];
	for(int i=1;i<(1<<n);i+=2)
		for(int j=0;j<n;j++)
			if(dp[i][j]>-1)
				for(int k=(1<<n)-1-i;k;k=(k-1)&(1<<n)-1-i)
					for(int l=0;l<n;l++)
						if(1<<l&k&&g[j][l]>-1)
							dp[i|k][l]=max(dp[i|k][l],dp[i][j]+g[j][l]+cost[k]);
	printf("%d\n",sum-dp[(1<<n)-1][n-1]);
	return 0;
}