#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;
class MaxFlow {
 public:
  int n, start, end, cap[20][20];
  vector<int> adj[20];
  void reset(int _n) {
    n = _n;
    for (int(i) = (0); (i) < (n); ++(i))
      for (int(j) = (0); (j) < (n); ++(j)) cap[i][j] = 0;
    for (int(i) = (0); (i) < (n); ++(i)) adj[i].clear();
  }
  void addEdge(int a, int b, int c) {
    adj[a].push_back(b);
    adj[b].push_back(a);
    cap[a][b] += c;
  }
  int bisa(void) {
    queue<pair<int, int> > q;
    int parent[n + 5];
    bool sudah[n + 5];
    memset(parent, -1, sizeof(parent));
    memset(sudah, 0, sizeof(sudah));
    q.push(make_pair(start, INF));
    parent[start] = -1;
    sudah[start] = 1;
    while (!q.empty()) {
      pair<int, int> now = q.front();
      q.pop();
      if (now.first == end) {
        int ix = now.first;
        while (ix != start) {
          cap[parent[ix]][ix] -= now.second;
          cap[ix][parent[ix]] += now.second;
          ix = parent[ix];
        }
        return now.second;
      }
      for (int(i) = (0); (i) < ((int)adj[now.first].size()); ++(i)) {
        int dest = adj[now.first][i];
        if (cap[now.first][dest] > 0) {
          int jalan = min(cap[now.first][dest], now.second);
          if (!sudah[dest]) {
            parent[dest] = now.first;
            sudah[dest] = 1;
            q.push(make_pair(dest, jalan));
          }
        }
      }
    }
    return 0;
  }
  int countMaxFlow(int s, int t) {
    start = s;
    end = t;
    int res = 0;
    while (1) {
      int x = bisa();
      if (x == 0) break;
      res += x;
    }
    return res;
  }
};
MaxFlow MF;
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 = 2140000000;
  for (int(bit) = (0); (bit) < (1 << n); ++(bit)) {
    if (bit & (1 << (n - 1))) continue;
    if (bit & (1 << 0)) {
      vector<int> a, b;
      vector<int> bisaa, bisab;
      bisaa.push_back(0);
      bisab.push_back(n - 1);
      for (int(i) = (0); (i) < (n); ++(i))
        if (bit & (1 << i))
          a.push_back(i);
        else
          b.push_back(i);
      int total = 0;
      for (int(i) = (0); (i) < ((int)a.size()); ++(i))
        for (int(j) = (0); (j) < ((int)b.size()); ++(j))
          total += cost[a[i]][b[j]];
      for (int(i) = (1); (i) < ((int)a.size()); ++(i)) {
        MF.reset((int)a.size());
        for (int(j) = (0); (j) < ((int)a.size()); ++(j))
          for (int(k) = (0); (k) < ((int)a.size()); ++(k))
            if (j != k && cost[a[j]][a[k]] > 0) MF.addEdge(j, k, 1);
        if (MF.countMaxFlow(0, i) == 1) bisaa.push_back(a[i]);
      }
      for (int(i) = (0); (i) < ((int)b.size() - 1); ++(i)) {
        MF.reset((int)b.size());
        for (int(j) = (0); (j) < ((int)b.size()); ++(j))
          for (int(k) = (0); (k) < ((int)b.size()); ++(k))
            if (j != k && cost[b[j]][b[k]] > 0) MF.addEdge(j, k, 1);
        if (MF.countMaxFlow(i, (int)b.size() - 1) == 1) bisab.push_back(b[i]);
      }
      for (int(i) = (0); (i) < ((int)bisaa.size()); ++(i))
        for (int(j) = (0); (j) < ((int)bisab.size()); ++(j))
          if (cost[bisaa[i]][bisab[j]] > 0)
            risan = min(risan, total - cost[bisaa[i]][bisab[j]]);
    }
  }
  printf("%d\n", risan);
  return 0;
}
