#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};


ll g[16][16];
ll sum[1 << 15];
ll dp[1 << 15][16];

void solve(ll N, ll M, vector<ll> a, vector<ll> b, vector<ll> c) {
  REP(i,N) REP(j,N) g[i][j] = int(-1e9);
  REP(i,N) g[i][i] = 0;
  REP(i,M) g[a[i] - 1][b[i] - 1] = c[i];
  REP(i,M) g[b[i] - 1][a[i] - 1] = c[i];

  REP(bit,1<<N) REP(i,N) REP(j,i) {
    if ((bit >> i) & (bit >> j) & 1)
      if (g[i][j] != int(-1e9)) sum[bit] += g[i][j];
  }

  REP(bit,1<<N) REP(i,N) dp[bit][i] = -1e9;
  REP(bit,1<<N) if (bit & 1) dp[bit][0] = sum[bit];
  REP(bit,1<<N) REP(i,N) REP(j,N) {
    if ((bit >> j) & 1) continue;
    int rest = (1 << N) - 1 - bit - (1 << j);
    for (int bit2 = rest; bit2 > 0; bit2 = (((bit2) - 1) & rest)) {
      chmax(dp[bit | (bit2 + (1 << j))][j], dp[bit][i] + sum[bit2 + (1 << j)] + g[i][j]);
    }
  }
  cout << accumulate(ALL(c), 0LL) - dp[(1 << N) - 1][N-1] << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	ll M;
	scanf("%lld", &N);
	scanf("%lld", &M);
	vector<ll> c(M-1+1);
	vector<ll> b(M-1+1);
	vector<ll> a(M-1+1);
	for (int i = 0 ; i <= M-1 ; i++) {
	  scanf("%lld", &a[i]);
	  scanf("%lld", &b[i]);
	  scanf("%lld", &c[i]);
	}
	solve(N, M, a, b, c);
	return 0;
}
