#include <iostream>
#include <vector>

#define MAXN 18
#define MAXX 36000000
using namespace std;

struct edge{
  int b, cost;
};

struct node{
  vector <edge> neighbours;
};

int dp[MAXN][1 << MAXN];
node graph[MAXN];

void addEdge(int a, int b, int cost) {
  graph[a].neighbours.push_back({b, cost});
}

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

  int n, m, i, a, b, cost, mask, ans, edgeCost;

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

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d%d", &a, &b, &cost);

    addEdge(a, b, cost);
  }

  for ( mask = 0; mask < (1 << n); mask++ ) {
    for ( i = 0; i < n; i++ ) {
      dp[i][mask] = MAXX + 1;
    }
  }

  dp[0][1] = 0;
  //for ( edge i : graph[0].neighbours )
    //dp[i.b][1 << i.b] = i.cost;

  for ( mask = 0; mask < (1 << n); mask++ ) {
    for ( i = 0; i < n; i++ ) {
      if ( mask & (1 << i) ) {
        for ( edge k : graph[i].neighbours ) {
          if ( mask & (1 << k.b) ) {
            dp[k.b][mask] = min(dp[i][mask], dp[i][mask - (1 << k.b)] + k.cost);
          }
        }
      }
    }
  }

  ans = MAXX + 1;
  for ( i = 0; i < n; i++ ) {
    edgeCost = MAXX + 1;
    for ( edge i2 : graph[i].neighbours ) {
      if ( i2.b == 0 )
        edgeCost = i2.cost;
    }

    ans = min(ans, dp[i][(1 << n) - 1] + edgeCost);
  }

  if ( ans != MAXX + 1 ) {
    fprintf(fout, "%d\n", ans);
  } else {
    fprintf(fout, "Nu exista solutie\n");
  }

  fclose(fin);
  fclose(fout);

  return 0;
}