#include <stdio.h>
#include <vector>
#include <algorithm>

FILE* fin;
FILE* fout;

const int MAX_N = 18;
const int INF = 1e9;

std::vector<int> adj[MAX_N];
int dp[1 << MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

int main() {
  fin = fopen("hamilton.in", "r");
  fout = fopen("hamilton.out", "w");

  int n, m;
  fscanf(fin, "%d%d", &n, &m);

  if(n == 1) {
    fprintf(fout, "1\n");
    return 0;
  }

  for(int i = 0; i < m; i++) {
    int u, v, c;
    fscanf(fin, "%d%d%d", &u, &v, &c);
    cost[u][v] = c;
    adj[u].push_back(v);
  }

  for(int mask = 0; mask < (1 << n); mask++) {
    for(int i = 0; i < n; i++) {
      dp[mask][i] = INF;
    }
  }
  dp[1][0] = 0;
  for(int mask = 0; mask < (1 << n); mask++) {
    for(int last = 0; last < n; last++) {
      if((mask >> last) & 1) {
        for(int v : adj[last]) {
          int c = cost[last][v];
          if(!((mask >> v) & 1)) {
            dp[mask | (1 << v)][v] = std::min(
              dp[mask | (1 << v)][v],
              dp[mask][last] + c
            );
          }
        }
      }
    }
  }

  int res = INF;
  for(int last = 0; last < n; last++) {
    if(cost[last][0] > 0) {
      int c = dp[(1 << n) - 1][last] + cost[last][0];
      res = std::min(res, c);
    }
  }

  fprintf(fout, "%d\n", res);

  fclose(fin);
  fclose(fout);

  return 0;
}