#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int MAX_N = 18;
const int INF = 2000000000;

struct Edge {
  int v, cost;
};

vector<Edge> neighbours[MAX_N];

int n;

int Backt[MAX_N][1 << MAX_N];

int backt(int u, int visited) {
  if (Backt[u][visited] == 0) {
    Backt[u][visited] = INF;
    if (visited == (1 << n) - 1 && u == 0)
      Backt[u][visited] = 0;
    else
      for (Edge e : neighbours[u])
        if ((visited & (1 << e.v)) == 0) // !visited[e.v]
                                         // ((visited >> e.v) & 1) == 0
          Backt[u][visited] = std::min(Backt[u][visited],
                                       e.cost + backt(e.v, visited ^ (1 << e.v)));
  }
  return Backt[u][visited];
}

int main() {
  int m;
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, cost;
    fin >> u >> v >> cost;
    neighbours[u].push_back({v,cost});
  }
  fout << backt(0, 0) << '\n';
  return 0;
}