#include <bits/stdc++.h>
using namespace std;
struct edge {
  int t, c;
  edge() {}
  edge(int tt, int cc) {
    t = tt;
    c = cc;
  }
};
vector<edge> G[20];
int n, m;
int a[500];
int b[500];
int c[500];
int dp[1 << 15][15];
int cost[1 << 15];
int dp2[1 << 15][15];
int node[15];
int node2[15];
int main(void) {
  int s = n, t = s + 1;
  scanf("%d%d", &n, &m);
  int sum = 0;
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &a[i], &b[i], &c[i]);
    a[i]--;
    b[i]--;
    sum += c[i];
    G[a[i]].push_back(edge(b[i], c[i]));
    G[b[i]].push_back(edge(a[i], c[i]));
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (!(i >> j & 1)) continue;
      for (int k = 0; k < G[j].size(); k++) {
        int nv = G[j][k].t;
        if (nv > j && ((i >> nv) & 1)) {
          cost[i] += G[j][k].c;
        }
      }
    }
  }
  memset(dp, -1, sizeof(dp));
  dp[1][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (dp[i][j] >= 0) {
        for (int k = 0; k < G[j].size(); k++) {
          int nv = G[j][k].t;
          int nc = G[j][k].c;
          if (!(i >> nv & 1)) {
            int nbit = i + (1 << nv);
            dp[i + (1 << nv)][nv] = max(dp[i + (1 << nv)][nv], dp[i][j] + nc);
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i < (1 << n); i++) {
    if (!(i >> 0 & 1)) continue;
    if (!(i >> (n - 1) & 1)) continue;
    int cnt = 0;
    int cnt2 = 0;
    for (int j = 0; j < n; j++) {
      if (i >> j & 1) {
        node[cnt++] = j;
      } else {
        node2[cnt2++] = j;
      }
    }
    for (int j = 0; j < (1 << cnt2); j++) {
      for (int k = 0; k <= cnt; k++) {
        dp2[j][k] = -1;
      }
    }
    dp2[0][0] = 0;
    for (int j = 0; j < cnt; j++) {
      for (int k = 0; k < (1 << cnt2); k++) {
        if (dp2[k][j] >= 0) {
          for (int l = k; l < (1 << cnt2); l = ((l + 1) | k)) {
            int rest = l - k;
            int bit = 1 << node[j];
            for (int lb = 0; lb < cnt2; lb++) {
              if (rest >> lb & 1) {
                bit += 1 << (node2[lb]);
              }
            }
            dp2[l][j + 1] = max(dp2[l][j + 1], dp2[k][j] + cost[bit]);
          }
        }
      }
    }
    if (dp[i][n - 1] >= 0 && dp2[(1 << cnt2) - 1][cnt] >= 0)
      res = max(res, dp[i][n - 1] + dp2[(1 << cnt2) - 1][cnt]);
  }
  printf("%d\n", sum - res);
  return 0;
}
