#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
int N, M;
long long E[16][16];
long long dp[1 << 15];
void _main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    E[a][b] = c;
    E[b][a] = c;
  }
  for (int i = 0; i < 1 << N; i++) dp[i] = INT_MAX / 2;
  dp[1] = 0;
  for (int mask = 0; mask < 1 << N; mask++)
    if (mask & 1) {
      for (int i = 1; i < N; i++)
        if ((mask & (1 << i)) == 0) {
          vector<long long> v;
          for (int j = 0; j < N; j++)
            if (mask & (1 << j)) {
              if (E[i][j]) v.push_back(E[i][j]);
            }
          sort(v.begin(), v.end());
          long long d = 0;
          for (int j = 1; j < v.size(); j++) d += v[j];
          dp[mask + (1 << i)] = min(dp[mask + (1 << i)], dp[mask] + d);
        }
    }
  for (int i = 0; i < 1 << N; i++)
    if (dp[i] != INT_MAX / 2) printf("%d : %lld\n", i, dp[i]);
  long long ans = INT_MAX / 2;
  for (int mask = 0; mask < 1 << N; mask++) {
    if ((mask & (1 << 0)) == 0) continue;
    if ((mask & (1 << (N - 1))) == 0) continue;
    long long d = dp[mask];
    for (int j = 0; j < N; j++)
      if ((mask & (1 << j)) == 0) {
        vector<long long> dd;
        for (int i = 0; i < N; i++)
          if (mask & (1 << i)) {
            dd.push_back(E[i][j]);
            d += E[i][j];
          }
        sort(dd.begin(), dd.end(), greater<long long>());
        d -= dd.front();
      }
    ans = min(ans, d);
  }
  cout << ans << endl;
}
