#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
typedef struct {
  int64_t a;
  int64_t b;
} hwll;
typedef struct {
  int64_t a;
  int64_t b;
  int64_t c;
} hwllc;
typedef struct {
  hwll a;
  hwll b;
} linell;
typedef struct {
  double a;
  double b;
} hwreal;
uint64_t n, m;
uint64_t h, w;
uint64_t k;
uint64_t q;
int64_t va, vb, vc, vd, ve, vf;
uint64_t ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;
uint64_t umin(uint64_t x, uint64_t y) { return (x < y) ? x : y; }
uint64_t umax(uint64_t x, uint64_t y) { return (x > y) ? x : y; }
int64_t smin(int64_t x, int64_t y) { return (x < y) ? x : y; }
int64_t smax(int64_t x, int64_t y) { return (x > y) ? x : y; }
uint64_t gcd(uint64_t x, uint64_t y) {
  if (x < y) {
    return gcd(y, x);
  } else if (y == 0) {
    return x;
  } else {
    return gcd(y, x % y);
  }
}
uint64_t bitpow(uint64_t a, uint64_t x, uint64_t modulo) {
  uint64_t result = 1;
  while (x) {
    if (x & 1) {
      result *= a;
      result %= modulo;
    }
    x /= 2;
    a = (a * a) % modulo;
  }
  return result;
}
uint64_t divide(uint64_t a, uint64_t b, uint64_t modulo) {
  return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}
uint64_t udiff(uint64_t a, uint64_t b) {
  if (a >= b) {
    return a - b;
  } else {
    return b - a;
  }
}
int64_t sdiff(int64_t a, int64_t b) {
  if (a >= b) {
    return a - b;
  } else {
    return b - a;
  }
}
int bitcount(uint64_t n) {
  int result = 0;
  while (n) {
    if (n & 1) result++;
    n /= 2;
  }
  return result;
}
int32_t pullcomp(const void *left, const void *right) {
  uint64_t l = *(uint64_t *)left, r = *(uint64_t *)right;
  if ((l) < (r)) return -1;
  if ((l) > (r)) return +1;
  return 0;
}
int32_t prevcomp(const void *left, const void *right) {
  int64_t l = *(int64_t *)left, r = *(int64_t *)right;
  if ((r) < (l)) return -1;
  if ((r) > (l)) return +1;
  return 0;
}
int32_t psllcomp(const void *left, const void *right) {
  int64_t l = *(int64_t *)left, r = *(int64_t *)right;
  if ((l) < (r)) return -1;
  if ((l) > (r)) return +1;
  return 0;
}
int32_t pcharcomp(const void *left, const void *right) {
  char l = *(char *)left, r = *(char *)right;
  if ((l) < (r)) return -1;
  if ((l) > (r)) return +1;
  return 0;
}
int32_t pdoublecomp(const void *left, const void *right) {
  double l = *(double *)left, r = *(double *)right;
  if ((l) < (r)) return -1;
  if ((l) > (r)) return +1;
  return 0;
}
int32_t pstrcomp(const void *left, const void *right) {
  char *l = *(char **)left;
  char *r = *(char **)right;
  return strcmp(l, r);
}
int32_t phwllABcomp(const void *left, const void *right) {
  hwll l = *(hwll *)left, r = *(hwll *)right;
  if ((l.a) < (r.a)) return -1;
  if ((l.a) > (r.a)) return +1;
  if ((l.b) < (r.b)) return -1;
  if ((l.b) > (r.b)) return +1;
  return 0;
}
int32_t phwllREVcomp(const void *left, const void *right) {
  hwll l = *(hwll *)left, r = *(hwll *)right;
  if ((l.b) < (r.b)) return -1;
  if ((l.b) > (r.b)) return +1;
  if ((l.a) < (r.a)) return -1;
  if ((l.a) > (r.a)) return +1;
  return 0;
}
int32_t ptriplecomp(const void *left, const void *right) {
  hwllc l = *(hwllc *)left, r = *(hwllc *)right;
  if ((l.a) < (r.a)) return -1;
  if ((l.a) > (r.a)) return +1;
  if ((l.b) < (r.b)) return -1;
  if ((l.b) > (r.b)) return +1;
  if ((l.c) < (r.c)) return -1;
  if ((l.c) > (r.c)) return +1;
  return 0;
}
int32_t ptripleREVcomp(const void *left, const void *right) {
  hwllc l = *(hwllc *)left, r = *(hwllc *)right;
  if ((l.b) < (r.b)) return -1;
  if ((l.b) > (r.b)) return +1;
  if ((l.a) < (r.a)) return -1;
  if ((l.a) > (r.a)) return +1;
  if ((l.c) < (r.c)) return -1;
  if ((l.c) > (r.c)) return +1;
  return 0;
}
int32_t phwrealcomp(const void *left, const void *right) {
  hwreal l = *(hwreal *)left, r = *(hwreal *)right;
  if ((l.a) < (r.a)) return -1;
  if ((l.a) > (r.a)) return +1;
  if ((l.b) < (r.b)) return -1;
  if ((l.b) > (r.b)) return +1;
  return 0;
}
int32_t pquadcomp(const void *left, const void *right) {
  linell l = *(linell *)left;
  linell r = *(linell *)right;
  int64_t ac = phwllABcomp(&(l.a), &(r.a));
  if (ac) return ac;
  int64_t bc = phwllABcomp(&(l.b), &(r.b));
  if (bc) return bc;
  return 0;
}
bool isinrange(int64_t left, int64_t x, int64_t right) {
  return (left <= x && x <= right);
}
bool isinrange_soft(int64_t left, int64_t x, int64_t right) {
  return (left <= x && x <= right) || (left >= x && x >= right);
}
int64_t a[1048576 + 5];
int64_t b[1048576 + 5];
int64_t c[1048576 + 5];
int64_t d[1048576 + 5];
int64_t e[1048576];
char s[3010][3010];
char t[1048576 + 1];
char u[1048576 + 1];
hwll xy[1048576 + 5];
hwllc tup[1048576 + 5];
uint64_t gin[1048576];
int64_t edges[20][20];
int64_t dp[1048576];
int64_t dfs(uint64_t con, uint64_t w, uint64_t v) {
  if (v < n) {
    if (con & (1LL << v)) {
      return dfs(con, w, v + 1);
    } else {
      return smin(dfs(con, w, v + 1), dfs(con, w | (1LL << v), v + 1));
    }
  }
  int64_t i, j;
  int64_t x = 0;
  for (i = 0; i < n; i++) {
    if ((i != 0) && (i != n - 1) && (con & (1LL << i))) continue;
    for (j = i + 1; j < n; j++) {
      if ((j != n - 1) && (con & (1LL << j))) continue;
      if (i == 0 && j == n - 1) continue;
      if (edges[i][j] < 0) continue;
      int64_t wi = ((w & (1LL << i)) ? 1 : 0);
      int64_t wj = ((w & (1LL << j)) ? 1 : 0);
      if (wi ^ wj) {
        x += edges[i][j];
      }
    }
  }
  return x;
}
uint64_t solve() {
  int64_t i, j, ki, li;
  int64_t result = 0;
  double dresult = 0;
  int64_t maybe = 0;
  int64_t sum = 0;
  int64_t item;
  int64_t *dpcell;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      edges[i][j] = -1;
    }
  }
  for (i = 0; i < m; i++) {
    edges[a[i]][b[i]] = edges[b[i]][a[i]] = c[i];
  }
  dp[1] = 0;
  for (i = 3; !(i >> n); i += 2) {
    dp[i] = 2000000000000007LL;
    for (j = 1; j < n; j++) {
      if (!(i & (1LL << j))) continue;
      if ((i & (1LL << (n - 1))) && j < n - 1) continue;
      uint64_t prev = (i ^ (1LL << j));
      maybe = dp[prev];
      int64_t maxe = 0;
      bool iscon = false;
      for (ki = 0; ki < n; ki++) {
        if (edges[ki][j] < 0) continue;
        if (prev & (1LL << ki)) {
          maxe = smax(maxe, edges[ki][j]);
          iscon = true;
          maybe += edges[ki][j];
        }
      }
      maybe -= maxe;
      if (iscon && maybe < dp[i]) dp[i] = maybe;
    }
  }
  result = 2000000000000007LL;
  for (i = 0; !(i >> n); i++) {
    if (!(i & (1LL << 0)) || !(i & (1LL << (n - 1)))) continue;
    maybe = dp[i];
    int64_t inout = 0;
    for (j = 0; j < n; j++) {
      if (!(i & (1LL << j)) || j == 0 || j == n - 1) continue;
      for (ki = 0; ki < n; ki++) {
        if ((i & (1LL << ki))) continue;
        if (edges[j][ki] >= 0) inout += edges[j][ki];
      }
    }
    int64_t d = dfs(i, 1, 0);
    result = smin(result, maybe + inout + d);
  }
  printf("%lld\n", result);
  return 0;
success:
  puts("Yes");
  return 0;
fail:
  puts("No");
  return 1;
}
int32_t main(int argc, char *argv[]) {
  int32_t i, j;
  n = 3;
  m = 0;
  scanf("%llu%llu", &n, &m);
  for (i = 0; i < m; i++) {
    scanf("%lld", &a[i]);
    scanf("%lld", &b[i]);
    scanf("%lld", &c[i]);
    a[i]--;
    b[i]--;
  }
  solve();
  return 0;
}
