// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
#include<bitset>
#include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
template < class T > ostream &operator<<(ostream &o, const stack<T> &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; }
template <class T, class Container, class Compare > ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
template <class T, class Container > ostream &operator<<(ostream &os, queue<T, Container> a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T > inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << endl; }
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
#define dump1D(...) (42)
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}


int n, m;
constexpr int S = 15;
int g[S][S];
ll dp[1 << S][S];
ll dp0[1 << S];

// smin, smax {{{
// clang-format off
template < class T, class U > inline void smin(T &a, const U &b) { a = a < (T) b ? a : b; }
template < class T, class U > inline void smax(T &a, const U &b) { a = a < (T) b ? b : a; }
// clang-format on
// }}}

ll sol(int s, int i) {
  if(i == n - 1) return 0;
  if(~dp[s][i]) return dp[s][i];
  ll res = -1e18;
  for(int t = s; t > 0; t = (t - 1) & s) {
    for(int j = 0; j < n; j++) if(t & (1 << j)) {
      if(t == s && j != n - 1) continue;
      if(g[i][j] == 0) continue;
      smax(res, dp0[t] + sol(s ^ t, j) + g[i][j]);
    }
  }
  return dp[s][i] = res;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> m;
  int a, b, c;
  ll sum = 0;
  memset(dp, -1, sizeof dp);
  for(int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    a--; b--;
    g[a][b] = c;
    g[b][a] = c;
    sum += c;
  }

  // 事前計算 // dpでもなんでもないけど
  for(int i = 0; i < 1 << n; i++) {
    for(int j = 0; j < n; j++) for(int k = j + 1; k < n; k++) {
      if(i & (1 << j)); else continue;
      if(i & (1 << k)); else continue;
      dp0[i] += g[j][k];
    }
  }

  int mask = (1 << n) - 1;
  ll ans = 0;
  for(int i = 0; i < 1 << n; i++) {
    if(i & 1); else continue;
    if(i & (1 << (n - 1))) continue;
    smax(ans, dp0[i] + sol(mask ^ i, 0));
  }

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



Measured memory_bytes: 4352