#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)
{
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;
}
}