#include <cstdio>
#include <cstring>

inline void CMax(int &a,int b){a<b?a=b:0;}
int n,m,G[15][15],g[1<<15],f[1<<15][15],Sum;

int main()
{
    scanf("%d%d",&n,&m),memset(f,-1,sizeof f),f[1][0]=0;
    for(int i=1,x,y,z;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z),--x,--y,Sum+=z,G[x][y]=G[y][x]=z;
        for(int j=0;j<(1<<n);++j)if((j>>x)&(j>>y)&1)g[j]+=z;
    }
    for(int i=1;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(~f[i][j])
            {
                for(int k=0;k<n;++k)
                    if(!(i>>k&1)&&G[j][k])
                        CMax(f[1<<k|i][k],f[i][j]+G[j][k]);
                for(int U=((1<<n)-1)^i,k=U;k;k=(k-1)&U)
                    CMax(f[i|k][j],f[i][j]+g[1<<j|k]);
            }
    return printf("%d\n",Sum-f[(1<<n)-1][n-1]),0;
}