#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int getbit(int x, int pos) { return (x >> (pos - 1)) & 1; }
template <class T>
void turn_on(T &x, int pos) {
  x = x | ((T)1 << (pos - 1));
}
template <class T>
void turn_off(T &x, int pos) {
  x = x & ~((T)1 << (pos - 1));
}
template <class T>
T sqr(T a) {
  return a * a;
}
struct edge {
  int u, v, w;
  edge() {}
  edge(int a, int b, int c) {
    u = a;
    v = b;
    w = c;
  }
};
int G1[40000], G2[40000], G3[40000], n, m, lab[17], res = inf;
int T[17], c[17][17];
vector<edge> e;
vector<int> a[17];
bool cmp(edge a, edge b) { return a.w > b.w; }
int findset(int u) { return lab[u] <= 0 ? u : lab[u] = findset(lab[u]); }
void uni(int s, int t) {
  if (lab[s] < lab[t])
    lab[t] = s;
  else if (lab[s] > lab[t])
    lab[s] = t;
  else {
    lab[s] = t;
    lab[t]--;
  }
}
int process(edge e) {
  int s = findset(e.u), t = findset(e.v);
  if (s == t) return 0;
  uni(s, t);
  return e.w;
}
int calc_1(int s) {
  int res = 0;
  for (int u = 1; u <= n; ++u) {
    for (int i = 0; i < (int)a[u].size(); ++i) {
      int v = a[u][i];
      res += c[u][v] * getbit(s, u) * (!getbit(s, v));
    }
  }
  return res;
}
int calc_2(int s) {
  memset(lab, 0, sizeof(lab));
  e.clear();
  int res = 0;
  for (int u = 1; u <= n; ++u) {
    if (getbit(s, u) == 0) continue;
    for (int i = 0; i < (int)a[u].size(); ++i) {
      int v = a[u][i];
      if (getbit(s, v)) {
        e.push_back(edge(u, v, c[u][v]));
        res += c[u][v];
      }
    }
  }
  res /= 2;
  sort(e.begin(), e.end(), cmp);
  for (int i = 0; i < (int)e.size(); ++i) res -= process(e[i]);
  return res;
}
int calc_3(int s) {
  int MAX1 = -inf, MAX2 = -inf;
  for (int i = 1; i <= n; ++i) {
    if (getbit(s, i)) {
      if (c[i][1] != 0) MAX1 = max(MAX1, c[i][1]);
      if (c[i][n] != 0) MAX2 = max(MAX2, c[i][n]);
    }
  }
  return max(-inf, MAX1 + MAX2);
}
void check() {
  int s0 = 0, s1 = 0, s2 = 0;
  for (int i = 1; i <= n; ++i) {
    if (T[i] == 0) turn_on(s0, i);
    if (T[i] == 1) turn_on(s1, i);
    if (T[i] == 2) turn_on(s2, i);
  }
  if (G3[s1] == -inf) {
    if (c[1][n] != 0) res = min(res, G1[s0] - c[1][n]);
  }
  res = min(res, (G1[s0] + G1[s1] + G1[s2]) / 2 - G3[s1] + G2[s1]);
}
void backtrack(int i) {
  for (int j = 0; j <= 2; ++j) {
    if (T[i] != -1 && T[i] != j) continue;
    int tmp = T[i];
    T[i] = j;
    if (i == n)
      check();
    else
      backtrack(i + 1);
    T[i] = tmp;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    c[v][u] = c[u][v] = w;
    a[u].push_back(v);
    a[v].push_back(u);
  }
  int t = (1 << n) - 1;
  for (int i = 0; i < (int)t; ++i) G1[i] = calc_1(i);
  for (int i = 0; i < (int)t; ++i) G2[i] = calc_2(i);
  for (int i = 0; i < (int)t; ++i) G3[i] = calc_3(i);
  memset(T, -1, sizeof(T));
  T[1] = 0;
  T[n] = 2;
  backtrack(1);
  cout << res;
}
