#include <bits/stdc++.h>
void upd(int &x, int y) { x = std::min(x, y); }
int input() {
  int n;
  std::cin >> n;
  return n;
}
int main() {
  int n, m;
  std::cin >> n >> m;
  constexpr int INF = 1e9;
  static int g[15][15];
  for (int i = 0; i < 15; i++) {
    for (int j = 0; j < 15; j++) {
      g[i][j] = INF;
    }
  }
  for (int i = 0; i < m; i++) {
    int u = input() - 1;
    int v = input() - 1;
    int w = input();
    g[u][v] = w;
    g[v][u] = w;
  }
  static int dp[1 << 15][15];
  for (int i = 0; i < 1 << 15; i++) {
    for (int j = 0; j < 15; j++) {
      dp[i][j] = 1e9;
    }
  }
  for (int i = 0; i < 1 << n; i++) {
    if ((i >> 0 & 1) && (~i >> (n - 1) & 1)) {
      dp[i][0] = 0;
    }
  }
  std::vector<int> score(1 << n);
  static int ccc[15][1 << 15];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1 << n; j++) {
      for (int k = 0; k < n; k++) {
        if ((j >> k & 1) && g[i][k] != INF) {
          ccc[i][j] += g[i][k];
        }
      }
    }
  }
  for (int i = 0; i < 1 << n; i++) {
    int k = ((1 << n) - 1) ^ i;
    int j = k;
    do {
      int cost = 0;
      for (int u = 0; u < n; u++) {
        if ((i >> u & 1)) {
          cost += ccc[u][j];
        }
      }
      for (int u = 0; u < n; u++) {
        if ((~i >> u & 1)) continue;
        for (int v = 0; v < n; v++) {
          if ((j >> v & 1) && g[u][v] != INF) {
            upd(dp[i | j][v], dp[i][u] - g[u][v] + cost);
          }
        }
      }
      j = (j - 1) & k;
    } while (j != 0);
  }
  std::cout << dp[(1 << n) - 1][n - 1] << std::endl;
}
