#include<bits/stdc++.h>
using namespace std;

int dp[1<<15][15];
int g[15][15];
int dis[1<<15];
int n,m,ans=0x3f3f3f3f,sum;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;a--;b--;
        g[a][b]=g[b][a]=c;
        sum+=c;
    }
    for(int s=0;s<1<<n;s++){
        for(int i=0;i<n;i++)if(s>>i&1){
            for(int j=i+1;j<n;j++)if(s>>j&1){
                dis[s]+=g[i][j];
            }
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=sum;
    for(int s=0;s<1<<n;s++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)if(!(s>>j&1)&&g[i][j]){
                dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]-g[i][j]);
            }
            int rs=(s^((1<<n)-1))|(1<<i);
            for(int j=rs;j;j=rs&(j-1)){
                dp[s|j][i]=min(dp[s|j][i],dp[s][i]-dis[j]);
            }
        }
    }
    for(int s=0;s<1<<n;s++){
        ans=min(ans,dp[s][n-1]);
    }
    cout<<ans<<endl;

    return 0;
}
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,a,b,c,sum,dis[17][17],v[1<<15],f[1<<15][17];

signed main()
{
    n=read(); m=read();
    const int N=1<<n;
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        sum+=dis[a][b]=dis[b][a]=read();
    }
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1)) continue;
            for (int k=0;k<j;k++)
            {
                if (!(i>>k&1)) continue;
                v[i]+=dis[j+1][k+1];
            }
        }
    }
    memset(f,-1,sizeof(f));
    f[1][1]=0;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1) || !~f[i][j+1]) continue;
            for (int k=0;k<n;k++)
            {
                if (i>>k&1 || !dis[j+1][k+1]) continue;
                f[i|(1<<k)][k+1]=max(f[i|(1<<k)][k+1],f[i][j+1]+dis[j+1][k+1]);
            }
            int tot=((N-1)^i)|(1<<j);
            for (int k=tot;k;k=(k-1)&tot)
            {
                if (!(k>>j&1)) continue;
                f[i|k][j+1]=max(f[i|k][j+1],f[i][j+1]+v[k]);
            }
        }
    }
    return !printf("%d\n",sum-f[N-1][n]);
}