#include <iostream>
#include <cstdio>
#include <cstdlib>
#define INF 307000000

using namespace std;

int cost[25][25], c[263000][25], *a[25], sol = INF;
int n, m;

void init() {
  for(int i = 0; i < n; i++)
    a[i] = (int *)calloc(1, sizeof(int));
}

void add(int x, int y) {
  a[x][0]++;
  a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
  a[x][a[x][0]] = y;
}

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

  scanf("%d %d", &n, &m);
  init();

  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      cost[i][j] = INF;
  for(int i = 0; i < 1 << n; i++)
    for(int j = 0; j < n; j++)
      c[i][j] = INF;

  for(int i = 1; i <= m; i++) {
    scanf("%d %d", &x, &y);
    scanf("%d", &cost[x][y]);
    add(y, x);
  }

  c[1][0] = 0;
  for(int i = 2; i < (1 << n); i++)
    for(int j = 0; j < n; j++)
      if(i & (1 << j))
        for(int k = 1; k <= a[j][0]; k++)
          if(i & (1 << a[j][k]))
            c[i][j] = min(c[i][j], c[i ^ (1 << j)][a[j][k]] + cost[a[j][k]][j]);

  x = (1 << n) - 1;
  for(int i = 1; i < n; i++)
    sol = min(sol, c[x][i] + cost[i][0]);
  printf("%d", sol);

  return 0;
}