#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int INF = 2e9;
unordered_map<int, int> cost[(1 << N) + 2];
int dp[(1 << N) + 2][N + 2];
int g[N + 2][N + 2];
int tmp[(1 << N) + 2];
int n, m, tp;
void update(int &x, int y) { x = min(x, y); }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    x--;
    y--;
    g[x][y] = g[y][x] = z;
  }
  for (int i = 0; i <= ((1 << n) - 1); i++) cost[i][0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) cost[(1 << i)][(1 << j)] = g[i][j];
  }
  for (int i = 0; i <= ((1 << n) - 1); i++) {
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) continue;
      int lb = i & (-i);
      cost[i][(1 << j)] = cost[i - lb][(1 << j)] + cost[lb][(1 << j)];
    }
  }
  for (int i = 0; i <= ((1 << n) - 1); i++) {
    int c = ((1 << n) - 1) - i;
    tp = 0;
    for (int j = c; j >= 0; j = (j == 0 ? -1 : (j - 1) & c)) {
      tp++;
      tmp[tp] = j;
    }
    for (int j = tp; j >= 1; j--) {
      int jj = tmp[j];
      for (int k = 0; k < n; k++) {
        if (jj & (1 << k))
          cost[i][jj] = cost[i][jj - (1 << k)] + cost[i][(1 << k)];
      }
    }
  }
  memset(dp, 42, sizeof(dp));
  dp[1][0] = 0;
  for (int i = 1; i <= ((1 << n) - 1); i += 2) {
    for (int j = 0; j < n; j++) {
      if ((i & (1 << j)) == 0) continue;
      for (int k = 0; k < n; k++) {
        if ((i & (1 << k)) == 0) {
          update(dp[i | (1 << k)][k], dp[i][j] + cost[i - (1 << j)][(1 << k)]);
        }
      }
      int c = ((1 << n) - 1) - i;
      for (int k = c; k >= 0; k = (k == 0 ? -1 : (k - 1) & c)) {
        update(dp[i | k][j], dp[i][j] + cost[(i - (1 << j))][k]);
      }
    }
  }
  printf("%d\n", dp[((1 << n) - 1)][n - 1]);
  return 0;
}
