#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
template <typename T>
using Graph = vector<vector<T>>;
template <typename T>
using Spacial = vector<vector<vector<T>>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
string interval[2] = {" ", "\n"};
template <typename T>
struct is_plural : false_type {};
template <typename T1, typename T2>
struct is_plural<pair<T1, T2>> : true_type {};
template <typename T>
struct is_plural<vector<T>> : true_type {};
template <typename T>
struct is_plural<complex<T>> : true_type {};
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  return is >> p.first >> p.second;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << p.first << " " << p.second;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  if (vec.empty()) return os;
  bool pl = is_plural<T>();
  os << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr)
    os << interval[pl] << *itr;
  return os;
}
bool CoutYN(bool a, string y = "Yes", string n = "No") {
  cout << (a ? y : n) << "\n";
  return a;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}
long long modpow(int a, long long n, int mod = MOD) {
  long long ret = 1;
  do {
    if (n & 1) ret = ret * a % mod;
    a = 1LL * a * a % mod;
  } while (n >>= 1);
  return ret;
}
template <typename T>
T GCD(T a, T b) {
  return b ? GCD(b, a % b) : a;
}
template <typename T>
T LCM(T a, T b) {
  return a / GCD(a, b) * b;
}
template <typename T1, typename T2>
bool CompareBySecond(pair<T1, T2> a, pair<T1, T2> b) {
  return a.second != b.second ? a.second < b.second : a.first < b.first;
}
template <typename T1, typename T2>
bool CompareByInverse(pair<T1, T2> a, pair<T1, T2> b) {
  return a.first != b.first ? a.first < b.first : a.second > b.second;
}
template <typename flow_t>
struct Dinic {
  const flow_t INF;
  struct edge {
    int to;
    flow_t cap;
    int rev;
    bool isrev;
    int idx;
  };
  vector<vector<edge>> graph;
  vector<int> min_cost, iter;
  Dinic(int V) : INF(numeric_limits<flow_t>::max()), graph(V) {}
  void add_edge(int from, int to, flow_t cap, bool undirected = false,
                int idx = -1) {
    graph[from].emplace_back(
        (edge){to, cap, (int)graph[to].size(), false, idx});
    graph[to].emplace_back((edge){from, undirected ? cap : 0,
                                  (int)graph[from].size() - 1, true, idx});
  }
  bool bfs(int s, int t) {
    min_cost.assign(graph.size(), -1);
    queue<int> que;
    min_cost[s] = 0;
    que.push(s);
    while (!que.empty() && min_cost[t] == -1) {
      int p = que.front();
      que.pop();
      for (auto &e : graph[p]) {
        if (e.cap > 0 && min_cost[e.to] == -1) {
          min_cost[e.to] = min_cost[p] + 1;
          que.push(e.to);
        }
      }
    }
    return min_cost[t] != -1;
  }
  flow_t dfs(int idx, const int t, flow_t flow) {
    if (idx == t) return flow;
    for (int &i = iter[idx]; i < graph[idx].size(); ++i) {
      edge &e = graph[idx][i];
      if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
        flow_t d = dfs(e.to, t, min(flow, e.cap));
        if (d > 0) {
          e.cap -= d;
          graph[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  flow_t max_flow(int s, int t) {
    flow_t flow = 0;
    while (bfs(s, t)) {
      iter.assign(graph.size(), 0);
      flow_t f = 0;
      while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
    return flow;
  }
};
template <typename T>
struct edge {
  int from, to;
  T cost;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  operator int() const { return to; }
  bool operator<(const edge<T> &e) const { return cost < e.cost; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<vector<edge<T>>>;
void solve() {
  int n, m;
  cin >> n >> m;
  WeightedGraph<int> g(n);
  for (int i = 0; i < (int)(m); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  WeightedGraph<int> dist(n, Edges<int>(1 << n, {-1, 0}));
  queue<pii> q;
  q.emplace(0, 1);
  while (!q.empty()) {
    int v, path;
    tie(v, path) = q.front();
    q.pop();
    for (auto &e : g[v]) {
      if (path & (1 << e.to)) continue;
      int nxt = path | (1 << e.to);
      if (dist[e.to][nxt].cost == 0 && e.to != n - 1) q.emplace(e.to, nxt);
      if (chmax(dist[e.to][nxt].cost, dist[v][path].cost + e.cost)) {
        dist[e.to][nxt].to = v;
      }
    }
  }
  int ans = 1e9;
  for (int i = (1 << n - 1) + 1; i < 1 << n; i += 2) {
    if (dist[n - 1][i].to == -1) continue;
    Dinic<int> dinic(n + 1);
    int cost = -dist[n - 1][i].cost;
    for (int j = 0; j < (int)(n); ++j) {
      bool u = (i >> j) & 1;
      for (auto &e : g[j]) {
        if (e.to < j) continue;
        bool v = (i >> e.to) & 1;
        if (u & v) {
          cost += e.cost;
        } else {
          dinic.add_edge(j, e.to, e.cost, true);
        }
      }
    }
    int v = n - 1, path = i;
    while (1) {
      int prev = dist[v][path].to;
      if (prev == -1) break;
      dinic.add_edge(v, n, numeric_limits<int>::max());
      cost += dinic.max_flow(prev, n);
      path ^= 1 << v;
      v = prev;
    }
    chmin(ans, cost);
  }
  cout << ans << endl;
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}
