#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"; }
};

class UnionFind {
  vector<int> p;
public:
  UnionFind (int n) : p(n, -1) {}
  int root(int x) {
    return p[x] < 0 ? x : p[x] = root(p[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};

ll g[16][16];

ll tree[1 << 15];
ll sum[1 << 15];

bool next(vector<int> &v) {
  const int n = v.size();
  for (int i = 0; i < n; ++i) {
    if (v[i] == 2) v[i] = 0;
    else { ++v[i]; return true; }
  }
  return false;
}

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) {
    vector<tuple<int,int,int>> edges;
    REP(i,N) REP(j,i)
      if ((bit >> i) & (bit >> j) & 1)
        if (g[i][j] != int(-1e9)) edges.emplace_back(g[i][j], i, j);
    sort(edges.rbegin(), edges.rend());
    UnionFind uf(N);
    ll weight = 0;
    for (auto t: edges) {
      int from, to, w;
      tie(w, from, to) = t;
      if (uf.unite(from, to)) weight += w;
    }
    if (uf.same(0, N - 1)) {
      tree[bit] = weight;
    }
    else {
      tree[bit] = -1e9;
    }
  }

  vector<int> vec(N - 2, 0);
  ll max_cap = 0;
  do {
    int bit_route = 0, bit1 = 0, bit2 = 0;
    REP(i,N-2) {
      if (vec[i] == 0) bit_route += (1 << (i + 1));
      if (vec[i] == 1) bit1 += (1 << (i + 1));
      if (vec[i] == 2) bit2 += (1 << (i + 1));
    }
    bit_route += (1 << 0) + (1 << (N - 1));
    bit1 += (1 << 0);
    bit2 += (1 << (N - 1));
    chmax(max_cap, tree[bit_route] + sum[bit1] + sum[bit2]);
    // if (tree[bit_route] + sum[bit1] + sum[bit2] == max_cap) {
    //   cout << bit_route << " " << bit1 << " " << bit2 << endl;
    //   cout << tree[bit_route] << " " << sum[bit1] << " " << sum[bit2] << endl;
    // }
  } while (next(vec));
  cout << accumulate(ALL(c), 0LL) - max_cap << 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;
}
