#include <bits/stdc++.h>
using namespace std;
int N, M;
int a[400];
int b[400];
long long c[400];
vector<pair<long long, int> > v;
int par1[1000];
int rank1[1000];
void init(int n) {
  for (int i = 0; i < n; i++) {
    par1[i] = i;
    rank1[i] = 0;
  }
}
int find(int x) {
  if (par1[x] == x) {
    return x;
  } else {
    return par1[x] = find(par1[x]);
  }
}
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (rank1[x] < rank1[y]) {
    par1[x] = y;
  } else {
    par1[y] = x;
    rank1[x]++;
  }
}
bool same(int x, int y) { return find(x) == find(y); }
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < (M); i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    v.push_back(pair<long long, int>(c[i], i));
  }
  sort(v.begin(), v.end(), greater<pair<long long, int> >());
  long long ans = 1e15;
  for (int i = 0; i < (1 << N); i++) {
    long long nn = i | (1 << (N - 1));
    nn |= 1;
    long long now = 0;
    init(20);
    for (int j = 0; j < (v.size()); j++) {
      int num = v[j].second;
      if (!((nn >> a[num]) & 1)) continue;
      if (!((nn >> b[num]) & 1)) continue;
      if (same(a[num], b[num])) {
        now += v[j].first;
      } else {
        unite(a[num], b[num]);
      }
    }
    if (same(0, N - 1) == false) continue;
    init(20);
    for (int j = 0; j < (v.size()); j++) {
      long long num = v[j].second;
      if (((nn >> a[num]) & 1) && ((nn >> b[num]) & 1)) continue;
      bool b1 = false, b2 = false;
      for (int k = 0; k < (N); k++) {
        if ((nn >> k) & 1) {
          if (same(k, a[num])) {
            b1 = true;
          }
          if (same(k, b[num])) {
            b2 = true;
          }
        }
      }
      if (same(a[num], b[num]) == false && b1 == true && b2 == true) {
        now += v[j].first;
      } else if (!same(a[num], b[num])) {
        unite(a[num], b[num]);
      }
    }
    ans = min(ans, now);
  }
  cout << ans << endl;
  return (0);
}
