#include <cstdio>
#include <memory>
#include <vector>
#include <algorithm>

using namespace std;

class Solver{
private:
  int N, M;
  const int INF = 0x3f3f3f3f;

  vector<vector<int>> Graph;
  // Graph[k] = [array of nodes where I could come from]

  vector<vector<int>> cost;
  // cost[i][j] = the cost of the edge i->j or INF if i->j doesn't exist
  
  vector<vector<int>> DP;
  // DP[mask][j] = min cost to start in node 0,
  // pass through bits in mask and finish in j
  // DP[1000..0][0] = 0; the starting point,
  // all other states are initialized with INF.
  // DP[mask][j] = min(DP[mask][j], DP[mask ^ (1<<j)][k] + cost[k][j]) for 1<<k in mask
  
  vector<vector<bool>> computed;
  // computed[i][j] = true iff DP[i][j] was calculated.
  
public:
  Solver() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void ReadGraph() {
    scanf("%d%d", &N, &M);
    cost.resize(N, vector<int>(N, INF));
    Graph.resize(N);
    int from, to, edgeCost;
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &from, &to, &edgeCost);
      Graph[to].emplace_back(from);
      cost[from][to] = edgeCost;
    }
  }
  void ComputeHamilton() {
    DP.resize(1<<N, vector<int>(N, INF));
    computed.resize(1<<N, vector<bool>(N, false));
    int best = INF;
    DP[1][0] = 0;
    computed[1][0] = true;
    
    for (auto k: Graph[0])
      best = min(best,
    		 hamilton((1<<N) -1, k) + cost[k][0]);
    if (best >= INF)
      printf("Nu exista solutie\n");
    printf("%d\n", best);
  }
  int hamilton(int mask, int j) {

    if (computed[mask][j])
      return DP[mask][j];

    if (mask == 0)
      return INF;

    if (mask != 1 && j == 0)
      return INF;

    for (auto k: Graph[j]) {
      if (mask & (1<<k))
	DP[mask][j] = min(DP[mask][j], hamilton(mask ^ (1<<j), k) + cost[k][j]);
    }

    computed[mask][j] = true;
    return DP[mask][j];
  }
};

int main()
{
  unique_ptr<Solver> s = make_unique<Solver>();
  s->ReadGraph();
  s->ComputeHamilton();
  return 0;
}