#include<bits/stdc++.h>
#define inf 1000000007
#define N 24
using namespace std;
long long  e[N],cnt[1050000],d[N][N],f[2][N][1050000];
int n,m,n1,n2;
inline const void read(int &a)
{
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
int main()
{
	int x,y,z;
	read(n);read(m);
	memset(e,0,sizeof(e));
	memset(d,0,sizeof(d));
	e[2]=1;
	for (int i=3;i<=n;i++)
		e[i]=e[i-1]<<1;
	for (int i=1;i<=e[n]-1;i++)
		for (int j=i;j>0;j>>=1)
			cnt[i]+=j&1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		d[i][j]=inf*(i!=j);
	for (int i=1;i<=m;i++)
	{
		read(x);read(y);read(z);
		x++;
		y++;
		d[x][y]=d[y][x]=z;
	}
	if(n==3)
	{
		cout<<(d[1][2]+d[2][3])*2<<endl;
		return 0;
	}
	for (int k=1;k<=n;k++)
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	if (d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j];
	n1=(n-2)/2;
	n2=n-2-n1;
	for (int q=0;q<=1;q++)
	{
		for (int i=2;i<=n;i++)
		for (int j=0;j<=e[n]-1;j++)
		f[q][i][j]=inf;
		if(q==0)
		for (int i=2;i<n;i++)
		f[0][i][e[i]]=d[1][i];
		if (q==1)
		for (int i=2; i<n; i++)
		f[1][i][e[i]]=d[n][i];
		for (int j=1; j<e[n]; j++)
		if (cnt[j]<n2)
		for (int i=2; i<n; i++)
		if (f[q][i][j] < inf)
		for (int k=2; k<n; k++)
		if (f[q][i][j]+d[i][k] < f[q][k][j|e[k]]) f[q][k][j|e[k]]=f[q][i][j]+d[i][k];
	}
	int ans=inf;
	for (int ast=0; ast<e[n]; ast++)
	if(cnt[ast]==n1)
	{
		int x=inf;
		for (int i=2; i<n; i++)
		if (ast&e[i])
		for (int j=2; j<n; j++)
		if (!(ast&e[j]))
		if (f[0][i][ast]+d[i][j]+f[1][j][e[n]-1-ast]<x) 
			x=f[0][i][ast]+d[i][j]+f[1][j][e[n]-1-ast];
		for (int i=2; i<n; i++)
		if (ast&e[i])
		for (int j=2; j<n; j++)
		if (!(ast&e[j]))
		if (x+f[1][i][ast]+d[i][j]+f[0][j][e[n]-1-ast]<ans)
			ans=f[1][i][ast]+d[i][j]+f[0][j][e[n]-1-ast]+x;
	}
	cout<<ans<<endl;
	return 0;
}