#include <bits/stdc++.h>
using namespace std;
struct edge {
  int k, w, next;
} e[1005];
int n, m, f[20][20][100005], home[20], cnt = -1;
bool vis[20][20][100005];
void add(int x, int y, int w) {
  cnt++;
  e[cnt].k = y;
  e[cnt].w = w;
  e[cnt].next = home[x];
  home[x] = cnt;
}
void dfs(int S, int s, int t) {
  if (vis[s][t][S]) return;
  vis[s][t][S] = vis[t][s][S] = 1;
  if (s == t) return;
  f[s][t][S] = 1e9;
  for (int i = (S - 1) & S; i; i = (i - 1) & S)
    if ((i & (1 << s - 1)) && !(i & (1 << t - 1))) {
      int x = S ^ i, sum = 0;
      for (int p = 1; p <= n; p++)
        if (i & (1 << p - 1)) {
          for (int j = home[p]; ~j; j = e[j].next)
            if (x & (1 << e[j].k - 1)) sum += e[j].w;
        }
      for (int p = 1; p <= n; p++)
        if (i & (1 << p - 1)) {
          for (int j = home[p]; ~j; j = e[j].next)
            if (x & (1 << e[j].k - 1) && f[s][t][S] > sum - e[j].w) {
              dfs(i, s, p);
              dfs(x, e[j].k, t);
              f[s][t][S] =
                  min(f[s][p][i] + f[e[j].k][t][x] + sum - e[j].w, f[s][t][S]);
              if (s == 1 && t == n && S == (1 << n) - 1 && f[s][t][S] < 50000) {
                cout << "";
              }
            }
        }
    }
  f[t][s][S] = f[s][t][S];
}
int main() {
  memset(home, -1, sizeof(home));
  scanf("%d%d", &n, &m);
  for (int i = 1, x, y, w; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &w);
    add(x, y, w);
    add(y, x, w);
  }
  dfs((1 << n) - 1, 1, n);
  printf("%d", f[1][n][(1 << n) - 1]);
  return 0;
}
