#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

int n,m,half,ans=INT_MAX;
int d[21][21];
int v[21],v2[21];
int order[21];

void dfs2(int x,int deep,int now)
{
	cout<<"OK";
	if(now>=ans)
	{
		return ;
	}
	if(deep==n-1)
	{
		ans=min(ans,now+d[x][1]);
		return ;
	}
	if(deep<=half)
	{
		for(int i=2;i<n;i++)
			if(!v2[i]&&order[i]<=half)
			{
				v2[i]=1;
				dfs2(i,deep+1,now+d[x][i]);
				v2[i]=0;
			}
	}
	else
	{
		
		for(int i=2;i<n;i++)
			if(!v2[i])
			{
				v2[i]=1;
				dfs2(i,deep+1,now+d[x][i]);
				v2[i]=0;
			}
	}
}

void dfs(int x,int deep,int now)
{
	if(deep==n)
	{
		//for(int i=1;i<=n;i++)
		//	cout<<order[i]<<" ";
		//cout<<now<<endl;
		dfs2(n,1,now);
		
	}
	if(x==n)
		return ;
	for(int i=2;i<=n;i++)
		if(!v[i])
		{
			v[i]=1;
			order[i]=deep;
			dfs(i,deep+1,now+d[x][i]);
			v[i]=0;
		}
}
int main()
{
	int i,j,k,l;
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	memset(v2,0,sizeof(v2));
	n=read(),m=read();
	if(n<=8)
	{
		half=(n-2)/2;
		for(i=1;i<=m;i++)
		{
			j=read(),k=read(),l=read();
			j++,k++;
			d[j][k]=d[k][j]=l;
		}
		for(i=1;i<=n;i++)
			d[i][i]=0;
		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					if(d[i][k]+d[k][j]<d[i][j])
						d[i][j]=d[i][k]+d[k][j];
		dfs(1,1,0);
		cout<<ans;
	}
	else if(m==n-1)
	{
		int in[21],a1,a2;
		ans=0;
		memset(in,0,sizeof(in));
		for(i=1;i<=m;i++)
		{
			j=read(),k=read(),l=read();
			j++,k++;
			if(j==1||k==1)
				a1=l;
			if(j==n||k==n)
				a2=l;
			in[j]++,in[k]++,ans+=l;
		}
		ans*=4;
		if(in[1]==1)
			ans-=2*a1;
		if(in[n]==1)
			ans-=2*a2;
		cout<<ans;
	}
 }