#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,map[16][16],x,y,z,mmh[1<<15][15],o[1<<15][15];
inline int work(int a,int b){
	int mmh=0;
	for (int i=0;i<n;i++)
	if ((a>>i)&1) mmh+=o[b][i];
	return mmh;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(map,0,sizeof(map));
	memset(mmh,63,sizeof(mmh));
	while(m--){
		scanf("%d%d%d",&x,&y,&z);x--;y--;
		map[x][y]=map[y][x]=z;
	}
	for (int i=0;i<(1<<n);i++)
	for (int j=0;j<n;j++){
		o[i][j]=0;
		for (int k=0;k<n;k++)
		if ((i>>k)&1) o[i][j]+=map[j][k];
	}
	mmh[1][0]=0;
	for (int i=0;i<(1<<n);i++)
	for (int j=0;j<n;j++)
	if ((i>>j)&1){
		for (int k=0;k<n;k++)
		if (map[j][k])
		if (!((i>>k)&1)) mmh[i|(1<<k)][k]=min(mmh[i|(1<<k)][k],mmh[i][j]+work(i,1<<k)-map[j][k]);
		
		int u=(1<<n)-1-i;
		for (int p=u;p;p=(p-1)&u) mmh[i|p][j]=min(mmh[i|p][j],mmh[i][j]+work(i^(1<<j),p));
	}
	printf("%d\n",mmh[(1<<n)-1][n-1]);
}