#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &num) {
  num = 0;
  T f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') num = num * 10 + ch - '0', ch = getchar();
  num *= f;
}
int power(int x, int k, int p) {
  int res = 1;
  for (; k; k >>= 1, x = 1ll * x * x % p)
    if (k & 1) res = 1ll * res * x % p;
  return res;
}
const int maxn = 16;
int n, m;
int arc[maxn];
int c[maxn][1 << maxn], f[1 << maxn][maxn];
int totc[1 << maxn], vis[1 << maxn];
void upd(int &x, int y) { x = min(x, y); }
int calc(int nS, int S) {
  if (!nS) return 0;
  if (vis[nS]) return totc[nS];
  vis[nS] = 1;
  int t = arc[nS & (-nS)];
  return totc[nS] = calc(nS ^ (1 << t), S) + c[t][S];
}
int main() {
  memset(f, 127, sizeof f);
  read(n);
  read(m);
  for (int(i) = (0); (i) < (n); (i)++) arc[1 << i] = i;
  for (int(i) = (1); (i) <= (m); (i)++) {
    int x, y, z;
    read(x);
    read(y);
    read(z);
    x--;
    y--;
    for (int(s) = (0); (s) < (1 << n); (s)++)
      if (s >> y & 1) c[x][s] += z;
    for (int(s) = (0); (s) < (1 << n); (s)++)
      if (s >> x & 1) c[y][s] += z;
  }
  f[1][0] = 0;
  for (int(s) = (1); (s) < (1 << n); (s)++)
    for (int(t) = (0); (t) < (n); (t)++) {
      for (int(u) = (0); (u) < (n); (u)++)
        if ((!(s >> u & 1)) && c[u][1 << t])
          upd(f[s | (1 << u)][u], f[s][t] + c[u][s ^ (1 << t)]);
      for (int nxts = ((1 << n) - 1) ^ s; nxts;
           nxts = (((1 << n) - 1) ^ s) & (nxts - 1)) {
        upd(f[s | nxts][t], f[s][t] + calc(nxts, s ^ (1 << t)));
      }
      for (int nxts = ((1 << n) - 1) ^ s; nxts;
           nxts = (((1 << n) - 1) ^ s) & (nxts - 1))
        vis[nxts] = 0;
    }
  printf("%d\n", f[(1 << n) - 1][n - 1]);
  return 0;
}
