#include <bits/stdc++.h>
using namespace std;
int N, M;
int mat[101][101];
signed long long dp[1 << 15][15];
int cost[1 << 15][15];
template <int um>
class UF {
 public:
  vector<int> par, rank;
  UF() {
    rank = vector<int>(um, 0);
    for (int i = 0; i < um; i++) par.push_back(i);
  }
  int operator[](int x) {
    return (par[x] == x) ? (x) : (par[x] = operator[](par[x]));
  }
  int operator()(int x, int y) {
    if ((x = operator[](x)) == (y = operator[](y))) return x;
    if (rank[x] > rank[y]) return par[x] = y;
    rank[x] += rank[x] == rank[y];
    return par[y] = x;
  }
};
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> M;
  for (i = 0; i < (M); i++) {
    cin >> x >> y >> r;
    mat[x - 1][y - 1] = r;
    mat[y - 1][x - 1] = r;
  }
  for (i = 0; i < (1 << N); i++)
    for (x = 0; x < (N); x++) dp[i][x] = 1LL << 60;
  for (i = 0; i < (1 << N); i++) {
    for (x = 0; x < (N); x++) {
      for (y = 0; y < (N); y++)
        if (i & (1 << y)) cost[i][x] += mat[x][y];
    }
  }
  dp[1][0] = 0;
  for (int mask = 0; mask < 1 << N; mask++) {
    for (x = 0; x < (N); x++)
      if ((mask & (1 << x)) && dp[mask][x] < 1LL << 60) {
        for (y = 0; y < (N); y++)
          if (mat[x][y] && (mask & (1 << y)) == 0) {
            int addco = cost[mask][y] - mat[x][y];
            dp[mask | (1 << y)][y] =
                min(dp[mask | (1 << y)][y], dp[mask][x] + addco);
          }
      }
  }
  signed long long mi = 1LL << 60;
  for (int mask = 0; mask < 1 << N; mask++) {
    signed long long cur = dp[mask][N - 1];
    int master[15] = {};
    memset(master, 0xff, sizeof(master));
    UF<15> uf;
    priority_queue<pair<int, int>> Q;
    for (x = 0; x < (N); x++)
      for (y = 0; y < (x); y++) {
        if ((mask & (1 << x)) == 0 || (mask & (1 << y)) == 0) {
          if (mat[x][y]) Q.push({mat[x][y], x * 100 + y});
        }
      }
    for (x = 0; x < (N); x++)
      if (mask & (1 << x)) master[x] = x;
    while (Q.size()) {
      int ad = Q.top().first;
      x = Q.top().second / 100;
      y = Q.top().second % 100;
      Q.pop();
      if (master[uf[x]] != -1 && master[uf[y]] != -1 &&
          master[uf[x]] != master[uf[y]]) {
        cur += ad;
      } else {
        if (master[uf[x]] != -1)
          master[uf[y]] = master[uf[x]];
        else
          master[uf[x]] = master[uf[y]];
        uf(x, y);
      }
    }
    mi = min(mi, cur);
  }
  cout << mi << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
