#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void setmax(T& a, T const& b) {
  a = max(a, b);
}
inline int singleton(int i) { return 1 << i; }
inline int setminus(int s, int t) { return s & ~t; }
inline int complement(int s, int n) { return setminus((1 << n) - 1, s); }
inline bool is_a(int i, int s) { return s & (1 << i); }
inline bool is_subset(int s, int t) { return (s | t) == t; }
inline bool is_disjoint(int s, int t) { return (s & t) == 0; }
int solve(int n, vector<vector<pair<int, int> > > const& g,
          vector<tuple<int, int, int> > const& edges) {
  vector<int> component_wieght(1 << n);
  for (int x = 0; (x) < int(1 << n); ++(x)) {
    for (auto edge : edges) {
      int a, b, c;
      tie(a, b, c) = edge;
      if (is_a(a, x) and is_a(b, x)) {
        component_wieght[x] += c;
      }
    }
  }
  function<int(int)> use_remaining_edges = [&](int used) {
    vector<int> cur(1 << n, -1), prv;
    cur[0] = 0;
    int acc = 0;
    for (int i = 0; (i) < int(n); ++(i))
      if (is_a(i, used)) {
        cur.swap(prv);
        cur.assign(1 << n, 0);
        int z = complement(used, n);
        for (int x = z; x != 0; x = (x - 1) & z) {
          for (int y = x; y != 0; y = (y - 1) & x)
            if (prv[y] != -1 and is_subset(acc, y)) {
              setmax(cur[x | singleton(i)],
                     prv[y] + component_wieght[setminus(x, y) | singleton(i)]);
            }
        }
        acc ^= singleton(i);
        used ^= singleton(i);
      }
    return cur[(1 << n) - 1];
  };
  int result = 0;
  int acc = 0;
  int used = 0;
  const int start = 0;
  const int goal = n - 1;
  vector<int> path_dp(1 << n, -1);
  function<void(int)> go = [&](int i) {
    if (acc < path_dp[used | (1 << i)]) return;
    path_dp[used | (1 << i)] = acc;
    used ^= 1 << i;
    if (i == goal) {
      setmax(result, acc + use_remaining_edges(used));
    } else {
      for (auto edge : g[i]) {
        int j, cost;
        tie(j, cost) = edge;
        if (used & (1 << j)) continue;
        acc += cost;
        go(j);
        acc -= cost;
      }
    }
    used ^= 1 << i;
  };
  go(start);
  int total_cost = 0;
  for (auto edge : edges) {
    total_cost += get<2>(edge);
  }
  return total_cost - result;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<pair<int, int> > > g(n);
  vector<tuple<int, int, int> > edges(m);
  for (int i = 0; (i) < int(m); ++(i)) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    edges[i] = {a, b, c};
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  int result = solve(n, g, edges);
  printf("%d\n", result);
  return 0;
}
