#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m,x,y,z,a[20][20],kk,f[20][40000],p[40000],sum;
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;for (int i=1;i<=m;i++){
		cin>>x>>y>>z;if (x>y)swap(x,y);a[x][y]+=z;sum+=z;
	}kk=1<<n;for (int l=1;l<kk;l++)
		for (int i=1;i<=n;i++)if (l&(1<<(i-1)))
			for (int j=1;j<=n;j++)if (l&(1<<(j-1)))p[l]+=a[i][j];
	memset(f,200,sizeof(f));
	for (int i=1;i<kk;i++)if (i&1)f[1][i]=p[i];
	for (int i=1;i<kk;i++)
		for (int x1=1;x1<=n;x1++)if (i&(1<<(x1-1))){
			int P=(kk-1)^i;
			for (int x2=1;x2<=n;x2++)if (a[min(x1,x2)][max(x1,x2)])
				for (int j=P;j;j=(j-1)&P)if (j&(1<<(x2-1)))
					f[x2][i|j]=max(f[x2][i|j],f[x1][i]+a[min(x1,x2)][max(x1,x2)]+p[j]);
		}cout<<sum-f[n][kk-1]<<endl;
}