#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}

//INSERT ABOVE HERE
const int MAX = 15;
const int INF = 1e9;
int es[MAX][MAX]={};
int cs[1<<MAX]={};
int dp[MAX][1<<MAX];

signed main(){
  int n,m;
  cin>>n>>m;

  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    es[a][b]=es[b][a]=c;
  }

  const int sz=1<<n;
  for(int bit=0;bit<sz;bit++)
    for(int i=0;i<n;i++)
      for(int j=0;j<i;j++)
        if((bit>>i)&(bit>>j)&1)
          cs[bit]+=es[i][j];

  memset(dp,-1,sizeof(dp));
  MFP([&](auto dfs,int v,int bit)->int{
        int &res=dp[v][bit];
        if(~res) return res;

        int cand=(sz-1)-bit;
        if(v==n-1) return res=cs[cand];

        res=-INF;
        for(int u=0;u<n;u++){
          if(!es[u][v]) continue;
          if((bit>>u)&1) continue;
          for(int nbit=cand;nbit;nbit=(nbit-1)&cand)
            if((nbit>>v)&(~nbit>>u)&1)
              chmax(res,dfs(u,bit|nbit)+es[v][u]+cs[nbit]);
        }
        return res;
      })(0,0);

  int ans=-dp[0][0];
  for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)
      ans+=es[i][j];

  cout<<ans<<endl;
  return 0;
}
