#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15;
const long long INF = 1e15 + 6;
long long adj[MAX_N][MAX_N];
long long cost[(1 << MAX_N)];
long long dp[(1 << MAX_N)][MAX_N];
int arr[MAX_N];
long long Cost(long long mask1, long long mask2) {
  return cost[mask1 | mask2] - cost[mask1] - cost[mask2];
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  int tot = 0;
  for (int i = 1; m >= i; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    adj[a][b] = adj[b][a] = c;
    tot += c;
    for (int mask = 0; (1 << MAX_N) > mask; mask++) {
      if (((1 << a) & mask) != 0 && ((1 << b) & mask) != 0) cost[mask] += c;
    }
  }
  for (int i = 0; (1 << n) > i; i++) {
    for (int j = 0; n > j; j++) {
      if (j)
        dp[i][j] = INF;
      else
        dp[i][j] = 0;
    }
  }
  long long ans = INF;
  for (int mask = 1; (1 << n) > mask; mask++) {
    for (int j = 0; n > j; j++) {
      if (dp[mask][j] != INF) {
        int id = 0;
        for (int k = 0; n > k; k++) {
          if (((1 << k) & mask) == 0) arr[id++] = (1 << k);
          if (((1 << k) & mask) == 0) {
            if (adj[j][k] != 0)
              dp[(1 << k) | mask][k] =
                  min(dp[(1 << k) | mask][k],
                      dp[mask][j] + Cost(mask - (1 << j), (1 << k)));
          }
        }
        for (int k = 0; (1 << id) > k; k++) {
          int mask2 = 0;
          for (int l = 0; id > l; l++) {
            if (((1 << l) & k) != 0) mask2 += arr[l];
          }
          dp[mask & mask2][j] = min(dp[mask & mask2][j],
                                    dp[mask][j] + Cost(mask - (1 << j), mask2));
        }
      }
    }
  }
  printf("%lld\n", dp[(1 << n) - 1][n - 1]);
}
