#include <bits/stdc++.h>
using namespace std;
long long d[1 << 15][15][15];
int a[20][20];
int n;
long long doit(int bit, int x, int y) {
  vector<int> a1, a2;
  int i, j, k, bx, by, bit1, bit2;
  int used[20];
  long long ans, sum, ma, tmp;
  if (x == y) return 0;
  if (d[bit][x][y] != -1) return d[bit][x][y];
  ans = (1LL << 60);
  for (k = (1 << n) - 1; k >= 0; k--) {
    k &= bit;
    if (((1 << x) & k) == 0) continue;
    if (((1 << y) & k) != 0) continue;
    a1.clear();
    a2.clear();
    for (j = 0; j < n; j++)
      if (((1 << j) & bit) != 0) {
        if (((1 << j) & k) != 0)
          a1.push_back(j);
        else
          a2.push_back(j);
      }
    ma = 0;
    sum = 0;
    for (i = 0; i < a1.size(); i++)
      for (j = 0; j < a2.size(); j++)
        if (a[a1[i]][a2[j]] != 0) {
          sum += a[a1[i]][a2[j]];
          if (a[a1[i]][a2[j]] > ma) {
            ma = a[a1[i]][a2[j]];
          }
        }
    if (sum == 0) continue;
    bit1 = 0;
    for (i = 0; i < a1.size(); i++) bit1 |= (1 << a1[i]);
    bit2 = 0;
    for (i = 0; i < a2.size(); i++) bit2 |= (1 << a2[i]);
    for (i = 0; i < a1.size(); i++)
      for (j = 0; j < a2.size(); j++)
        if (a[a1[i]][a2[j]] == ma) {
          bx = a1[i];
          by = a2[j];
          tmp = sum - ma;
          tmp += doit(bit1, x, bx);
          tmp += doit(bit2, by, y);
          if (tmp < ans) {
            ans = tmp;
          }
        }
  }
  d[bit][x][y] = ans;
  return ans;
}
int main() {
  int i, j, k, x, y, z, m;
  long long ans, sum, ma;
  vector<int> b1, b2;
  scanf("%d%d", &n, &m);
  memset(a, 0, sizeof(a));
  for (i = 0; i < m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    x--;
    y--;
    if (a[x][y] != 0) printf("wa!!!%d %d\n", x, y);
    a[x][y] = z;
    a[y][x] = z;
  }
  memset(d, -1, sizeof(d));
  ans = doit((1 << n) - 1, 0, n - 1);
  printf("%lld\n", ans);
  return 0;
}
