#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int infi = 1 << 30;
int dist[32][32], d[20][300000];
vector<int> G[32];

int main() {
  freopen("hamilton.in", "r", stdin);
  freopen("hamilton.out", "w", stdout);

  int N, M;
  scanf("%d %d", &N, &M);

  for(int i = 0; i < N; ++ i)
    for(int mask = 1; mask < (1 << N); ++ mask)
      d[i][mask] = infi;

  for(int i = 1; i <= M; ++ i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    G[a].push_back(b);
    dist[a][b] = c;
  }

  d[0][1] = 0;
  for(int mask = 1; mask < (1 << N); ++ mask) {
    for(int i = 0; i < N; ++ i) {
      if(mask & (1 << i)) {
        for(auto it: G[i]) {
          if((mask & (1 << it)) == 0)
            d[it][mask + (1 << it)] = min(d[it][mask + (1 << it)], d[i][mask] + dist[i][it]);
        }
      }
    }
  }

  int ans = infi;
  for(int i = 1; i < N; ++ i) {
    int p = 0;
    for(auto it: G[i]) {
      if(it == 0) {
        p = dist[i][0];
        break;
      }
    }
    if(p > 0)
      ans = min(ans, d[i][(1 << N) - 1] + p);
  }


  printf("%d\n", ans);
  return 0;
}