#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, k, a[N], p2, T[N], E[N * N][3], ans = 1 << 30;
struct node {
  int c, a, b;
  bool operator<(const node &o) const { return c > o.c; }
} ed[N * N];
int Findx(int x) {
  if (T[x] == -1) return x;
  return T[x] = Findx(T[x]);
}
void Merge(int a, int b) {
  int x = Findx(a), y = Findx(b);
  if (x != y) T[x] = y;
}
void solve() {
  memset(T, -1, sizeof(T));
  int i, j, now = 0;
  k = 0;
  for (i = 1; i <= m; i++) {
    if (a[E[i][0]] == 2 && a[E[i][1]] == 2)
      ed[++k] = (node){E[i][2], E[i][0], E[i][1]};
    else if (a[E[i][0]] != a[E[i][1]])
      if (a[E[i][0]] == 2 || a[E[i][1]] == 2)
        if ((a[E[i][0]] == 1 && E[i][1] == 1) ||
            (a[E[i][1]] == 1 && E[i][0] == 1) ||
            (a[E[i][0]] == 3 && E[i][1] == n) ||
            (a[E[i][1]] == 3 && E[i][0] == n))
          ;
        else
          now += E[i][2];
      else
        now += E[i][2];
  }
  sort(ed + 1, ed + 1 + k);
  for (i = 1, j = 0; i <= k; i++)
    if (Findx(ed[i].a) != Findx(ed[i].b))
      Merge(ed[i].a, ed[i].b), j++;
    else
      now += ed[i].c;
  if (j == p2 - 1) ans = min(ans, now);
}
void dfs(int i) {
  if (i >= n) {
    solve();
    return;
  }
  for (int j = 1; j <= 3; j++) {
    a[i] = j;
    if (j == 2) p2++;
    dfs(i + 1);
    if (j == 2) p2--;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) cin >> E[i][0] >> E[i][1] >> E[i][2];
  a[1] = a[n] = 2;
  p2 = 2;
  dfs(2);
  cout << ans;
  return 0;
}
