#include <bits/stdc++.h>
int max(int a, int b) { return a > b ? a : b; }
int dsu[15];
int find(int i) { return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i])); }
int join(int i, int j) {
  i = find(i);
  j = find(j);
  if (i == j) return 0;
  if (dsu[i] > dsu[j])
    dsu[i] = j;
  else {
    if (dsu[i] == dsu[j]) dsu[i]--;
    dsu[j] = i;
  }
  return 1;
}
int main() {
  static int dp[1 << 15], dq[1 << 15];
  static char used[15];
  int n, m, k, sum;
  scanf("%d%d", &n, &m);
  memset(dp, -1, (1 << n) * sizeof *dp), dp[0] = 0;
  memset(dsu, -1, n * sizeof *dsu);
  k = 0, sum = 0;
  used[0] = 1, k++;
  while (m--) {
    int i, j, w, b;
    scanf("%d%d%d", &i, &j, &w), i--, j--;
    sum += w;
    if (!used[i]) used[i] = 1, k++;
    if (!used[j]) used[j] = 1, k++;
    if (join(i, j)) k--;
    memset(dq, -1, (1 << n) * sizeof *dq);
    for (b = 0; b < 1 << n; b++)
      if (dp[b] != -1) {
        dq[b] = max(dq[b], dp[b]);
        dq[b ^ 1 << i ^ 1 << j] = max(dq[b ^ 1 << i ^ 1 << j], dp[b] + w);
      }
    memcpy(dp, dq, (1 << n) * sizeof *dq);
  }
  printf("%d\n", k == 1 ? sum * 2 - dp[0] : -1);
  return 0;
}
