#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const ll N=13;
const ll M=1<<12+1;
const ll INF=1e9;
ll n,m=0,i,j,x,y,a[N][N],cnt,f[N][M],w[M][N],ans=LONG_LONG_MAX,ex[M];
ll pow2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
vector<ll> check[M],p[M];
void init()
{
    for(ll j=0;j< 1<<n;j++)
    {
        ex[j]=j;
        for(ll k=1;k<=n;k++)
            if((j>>(k-1))&1)
            {
                w[j][k]=0;;
                for(ll u=1;u<=n;u++)
                {
                    if(k!=u&&a[k][u]!=INF) 
                    {
                        ex[j]|=1<<(u-1);
                        w[j][u]=min(w[j][u],a[k][u]);
                    }
                }
            }
    }
    for(ll j=0;j< 1<<n;j++)
        for(ll k=0;k< 1<<n;k++)
        {
            if((j&k)==k&&(j&ex[k])==j)
            {
            //  cout<<j<<' '<<k<<endl;
                check[j].push_back(k);
                ll cost=0;
                for(ll u=1;u<=n;u++)
                if((j^k)>>(u-1)&1)
                cost+=w[k][u];
                p[j].push_back(cost);
            }
        }
}
int main()
{
//  std::ios::sync_with_stdio(false); 
//  freopen("P3959_1.in","r",stdin);
    cin>>n>>m;
    memset(f,0x3f,sizeof f);
    memset(w,0x3f,sizeof w);
    memset(ex,0x3f,sizeof ex);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            a[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;cin>>j;
        a[x][y]=min(a[x][y],j);
        a[y][x]=a[x][y];
    }
//  for(i=0;i<(1<<n);i++)
//  {
//      cnt=0;
//      for(j=0;j<n;j++)
//          if(i>>j&1)cnt++;
//      q[cnt].push_back(i);
//  }
    init();
    for(i=1;i<=n;i++)f[1][1<<(i-1)]=0;
    //cout<<ex[3]<<endl;
    for(i=2;i<=n;i++)
    {
        for(j=0;j< 1<<n;j++)
        {
            for(ll k=0;k<check[j].size();k++)
            {
            //  cout<<j<<" "<<check[j][k]<<endl;
                f[i][j]=min(f[i][j],f[i-1][check[j][k]]+p[j][k]*(i-1));
            //  cout<<f[i][j]<<" "<<j<<" "<<check[j][k]<<" "<<p[j][k]<<" "<<i<<" "<<f[i-1][check[j][k]]<<endl;
            }
        }
    }
    for(i=1;i<=n;i++)ans=min(ans,f[i][(1<<n)-1]);//,cout<<f[i][(1<<n)-1]<<" "<<(1<<n)-1<<" "<<ans<<endl;
    cout<<ans<<endl;
    return 0;
}