#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
const int MaxN = 15;
const int INF = 1e9;
int n, m;
int sum[1 << MaxN];
int a[MaxN][MaxN];
int dp[1 << MaxN][MaxN];
int getDif(int mask1, int mask2) {
  return sum[mask1 | mask2] - sum[mask1] - sum[mask2];
}
void up(int& x, int y) {
  if (y < x) x = y;
}
void print(int mask) {
  for (int i = 0; i < n; ++i) cout << ((mask & (1 << i)) > 0);
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    --x, --y;
    a[x][y] = a[y][x] = z;
  }
  for (int mask = 0; mask < (1 << n); ++mask)
    for (int bit = 0; bit < n; ++bit)
      if (mask & (1 << bit))
        for (int otherBit = bit + 1; otherBit < n; ++otherBit)
          if (mask & (1 << otherBit)) sum[mask] += a[bit][otherBit];
  for (int mask = 0; mask < (1 << n); ++mask)
    for (int i = 0; i < n; ++i) dp[mask][i] = INF;
  dp[1][0] = 0;
  for (int mask = 1; mask < (1 << n); ++mask)
    for (int bit = 0; bit < n; ++bit)
      if (mask & (1 << bit) && dp[mask][bit] != INF) {
        for (int otherBit = 0; otherBit < n; ++otherBit)
          if (!(mask & (1 << otherBit)))
            up(dp[mask | (1 << otherBit)][otherBit],
               dp[mask][bit] + getDif(mask - (1 << bit), (1 << otherBit)));
        int otherMask = (1 << n) - 1 - mask;
        for (int subMask = otherMask; subMask; --subMask, subMask &= otherMask)
          up(dp[mask | subMask][bit],
             dp[mask][bit] + getDif(mask - (1 << bit), otherMask));
      }
  cout << dp[(1 << n) - 1][n - 1] << '\n';
  return 0;
}
