#include <bits/stdc++.h>
using namespace std;
double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};
inline string IntToString(long long a) {
  char x[100];
  sprintf(x, "%lld", a);
  string s = x;
  return s;
}
inline long long StringToInt(string a) {
  char x[100];
  long long res;
  strcpy(x, a.c_str());
  sscanf(x, "%lld", &res);
  return res;
}
inline string GetString(void) {
  char x[1000005];
  scanf("%s", x);
  string s = x;
  return s;
}
inline string uppercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}
inline string lowercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}
inline void OPEN(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
int cost[20][20];
int n, m, a, b, c;
vector<int> satu, dua, tiga;
unordered_map<int, int> dp[20];
int jahja(int now, int mask) {
  if (mask == (1 << (int)tiga.size()) - 1) {
    if (cost[tiga[now]][n - 1] == 0) return -INF;
    return cost[tiga[now]][n - 1];
  }
  int &ret = dp[now][mask];
  for (int(i) = (0); (i) < ((int)tiga.size()); ++(i))
    if (!(mask & (1 << i))) {
      int a = tiga[now];
      int b = tiga[i];
      if (cost[a][b] > 0)
        ret = max(ret, jahja(i, mask | (1 << i)) + cost[a][b]);
    }
  return ret;
}
int main() {
  scanf("%d %d", &n, &m);
  while (m--) {
    scanf("%d %d %d", &a, &b, &c);
    --a;
    --b;
    cost[a][b] = cost[b][a] = c;
  }
  int risan = INF;
  for (int(bit1) = (0); (bit1) < (1 << n); ++(bit1)) {
    if (!(bit1 & (1 << 0))) continue;
    if ((bit1 & (1 << (n - 1)))) continue;
    satu.clear();
    vector<int> sisa;
    for (int(i) = (0); (i) < (n); ++(i))
      if (bit1 & (1 << i))
        satu.push_back(i);
      else
        sisa.push_back(i);
    reverse(sisa.begin(), sisa.end());
    for (int(bit2) = (0); (bit2) < (1 << (int)sisa.size()); ++(bit2)) {
      if (!(bit2 & (1 << 0))) continue;
      dua.clear();
      tiga.clear();
      for (int(i) = (0); (i) < ((int)sisa.size()); ++(i))
        if (bit2 & (1 << i))
          dua.push_back(sisa[i]);
        else
          tiga.push_back(sisa[i]);
      int total = 0;
      for (int(i) = (0); (i) < ((int)satu.size()); ++(i))
        for (int(j) = (0); (j) < ((int)dua.size()); ++(j)) {
          total += cost[satu[i]][dua[j]];
        }
      for (int(i) = (0); (i) < ((int)satu.size()); ++(i))
        for (int(j) = (0); (j) < ((int)tiga.size()); ++(j)) {
          total += cost[satu[i]][tiga[j]];
        }
      for (int(i) = (0); (i) < ((int)dua.size()); ++(i))
        for (int(j) = (0); (j) < ((int)tiga.size()); ++(j)) {
          total += cost[dua[i]][tiga[j]];
        }
      for (int(i) = (0); (i) < ((int)tiga.size()); ++(i))
        for (int(j) = (i + 1); (j) < ((int)tiga.size()); ++(j))
          total += cost[tiga[i]][tiga[j]];
      for (int(i) = (0); (i) < ((int)tiga.size()); ++(i)) dp[i].clear();
      int maks = -INF;
      if ((int)tiga.size() == 0) {
        maks = (cost[0][n - 1] == 0 ? -INF : cost[0][n - 1]);
      }
      for (int(i) = (0); (i) < ((int)tiga.size()); ++(i)) {
        if (cost[0][tiga[i]] > 0)
          maks = max(maks, cost[0][tiga[i]] + jahja(i, 1 << i));
      }
      risan = min(risan, total - maks);
    }
  }
  printf("%d\n", risan);
  return 0;
}
