#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 15
int g[MN+5][MN+5],F[1<<MN][MN+5];
ll f[1<<MN][MN+5];
vector<int> v[1<<MN];
inline void rw(ll&a,ll b){if(b>a)a=b;}
int main()
{
	int n,m,i,j,k,x,y,s=0;
	n=read();m=read();
	while(m--)x=read(),y=read(),s+=g[x][y]=g[y][x]=read();
	for(i=1;i<1<<n;++i)for(j=1;j<=n;++j)if(i&(1<<j-1))
	{
		v[i].push_back(j);
		i^=1<<j-1;
		for(x=0;x<v[i].size();++x)
		{
			F[i^(1<<j-1)][j]+=g[v[i][x]][j];
			for(y=0;y<x;++y)F[i^(1<<j-1)][j]+=g[v[i][x]][v[i][y]];
		}
		i^=1<<j-1;
	}
	memset(f,200,sizeof(f));
	for(i=1;i<1<<n;++i)if(i&1)f[i][1]=F[i][1];
	for(i=1;i<1<<n;++i)for(j=0;j<v[i].size();++j)
		for(x=i^(1<<v[i][j]-1);x&=i^(1<<v[i][j]-1);--x) 
			for(y=0;y<v[x].size();++y)if(g[v[i][j]][v[x][y]])
				rw(f[i][v[i][j]],f[x][v[x][y]]+g[v[i][j]][v[x][y]]+F[i^x][v[i][j]]);
	printf("%d",s-f[(1<<n)-1][n]);
}