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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

const ll maxn=1<<15;
ll dist[105][105];
ll dp[maxn][15];    // 集合sに対応する頂点群に対し、頂点1=>vに移動する同一頂点を2回以上通らない経路が一通りになる状態の最小コスト

// dp[s][v]からの遷移は2通り考えられる
// (1) v=>v'への経路の延長
// (2) sに含まれない頂点群をvと連結させる
// 正確には(vとの辺の存在しないかもしれないため)vと連結されるかは定かではない
// まず自明に、補集合bitmaskとsにある辺はできるだけ取り除かないほうがコストが小さくなる
// しかし、1=>vの間にサイクルができてしまうと条件を満たさないので、
// 既に求まっているdp[s][v](サイクルがない1=>v間の最小コスト)に対応するグラフの終点vのみに対し、補集合の頂点を辺があれば連結するようにする
// この(2)の遷移を(1)の遷移と同時に小さい集合から求めていくと、同じ頂点集合のなかでも有り得る辺の組合せ全てを考慮することになる
// (例として、3つの頂点があり、それぞれの頂点間に辺がある場合を考えるとわかりやすい)
// また、これはsの補集合をsubmaskとすると、dp[s][v]からdp[s|submask][v]を求めることに相当する
// sとその補集合の列挙はO(N^3)で行える
// 類題
// https://yukicoder.me/problems/no/719
// https://atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c


ll cost[maxn][15];  // 集合s-頂点v間に存在する辺のコストの合計

// dpの2つ目の遷移で、submaskとvを連結させ、v以外の頂点とは連結させない、場合のコストを前計算しておく
// この前計算の計算量は O(2^N * N^2)

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  
  rep(i,m){
    ll x,y,r; cin>>x>>y>>r;
    x--,y--;
    dist[x][y]=dist[y][x]=r;
  }
  
  // cost[s][x]
  // 集合s-頂点x間の辺のコストの合計
  // この前計算により、今見ている集合sの頂点xから、sの補集合の頂点yへ辺を張る際のコストは、cost[s][y]-dist[x][y] と求めることができる
  rep(s,1<<n){
    rep(x,n) rep(y,n) if(s>>y&1) cost[s][x]+=dist[x][y];
  }
  
  rep(s,1<<n) rep(v,n) dp[s][v]=INF;
  dp[1][0]=0;
  
  
  for(ll s=0; s<(1<<n); s++){
    // x => y へとグラフを延長することを考える
    // x: 集合sからの延長元となる頂点
    rep(x,n) if((s>>x&1) && dp[s][x]!=INF){
      
      // 遷移(1) ... v=>v'への頂点の延長
      // y: 集合sからの延長先となる頂点。つまりsの補集合の頂点(ここでは更にxとの辺があるものに限られる)
      rep(y,n) if(((s>>y&1)==0) && dist[x][y]){
        // (集合s-頂点y間のコスト)-(x-y間のコスト)=延長に必要なコスト
        ll addcost=cost[s][y]-dist[x][y];
        chmin(dp[s|(1<<y)][y],dp[s][x]+addcost);
      }
      
      // 遷移(2) ... dp[s][v]のvへsの補集合submaskの頂点を連結する(v以外への頂点との辺を張らないことを確約する)
      ll nmask=s^(1<<x);    // sのうち、xを除く頂点集合
      ll left=((1<<n)-1)^s; // sの補集合
      // このループにおいてsubmaskは、sの全ての部分集合を表す
      for(ll submask=left; submask>0; submask=(submask-1)&left){
        // submask=(submask-1)&left の部分は以下の操作と同値
        // submask-- => submask&=left
        
        // vとsubmaskの頂点を連結する
        // 言い換えれば、sのv以外の頂点とsubmaskの頂点の間に辺を張らないことを確約することになるので、
        // 「sのv以外の頂点とsubmaskの頂点の間」の辺のコストの総和をここで求めている
        ll add=0;
        rep(y,n) if(submask&(1<<y)) add+=cost[nmask][y];
        
        dp[s|submask][x]=min(dp[s|submask][x], dp[s][x]+add);
      }
    }
  }
  
  cout<<dp[(1<<n)-1][n-1]<<endl;
  
}


Measured memory_bytes: 7936