#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  int a[m], b[m], c[m];
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
  }
  int minSum = 1e9;
  for (int mask = 0; mask < (1 << n); mask++) {
    if ((mask & 1) == 0) continue;
    if ((mask & (1 << (n - 1))) != 0) continue;
    for (int submask = mask; submask >= 0; submask = (submask - 1) & mask) {
      if (__builtin_popcount(mask ^ submask) == 1) {
        int sum = 0;
        for (int i = 0; i < m; i++)
          if ((mask & (1 << a[i])) && !(submask & (1 << b[i]))) sum += c[i];
        minSum = min(minSum, sum);
      }
      if (submask == 0) break;
    }
  }
  cout << minSum << endl;
  return 0;
}
