#include <bits/stdc++.h>

using namespace std;
const int VMAX = 20;
const int MASK = (1 << VMAX);
const int INF = 1e9;

struct def_edge {
   int to, cost;
}; vector<def_edge> g[1 + VMAX]; int V, E;
static inline void minSelf (int& a, int b) {
    if (a > b) a = b;
}

int dp[VMAX][MASK]; /// dp[node][mask] = costul minim pe drumul node -> 0 fara nodurile din mask
bool computed[VMAX][MASK];
int solve(int root, int mask) {
   if (computed[root][mask])
     return dp[root][mask];
   if (mask == (1 << V) - 1) { /// am eliminat toate nodurile
      if (root == 0) /// ciclu eulerian
        dp[root][mask] = 0;
      else
        dp[root][mask] = INF;
      computed[root][mask] = true;
   }
   else {
     for (def_edge e : g[root])
        if ( !(mask & (1 << e.to)) )
          minSelf (dp[root][mask], solve (e.to, mask ^ (1 << e.to)) + e.cost);
   }
   computed[root][mask] = true; return dp[root][mask];
}
int main()
{
    ifstream in ("hamilton.in");
    ofstream out ("hamilton.out");

    in >> V >> E;
    for (int i = 0; i < E; i ++) {
       int u, v, cost; in >> u >> v >> cost;
       g[u].push_back ({v, cost});
    }
    for (int node = 0; node < V; node ++)
       for (int mask = 0; mask < (1 << V); mask ++)
          dp[node][mask] = INF;
    out << solve (0, 0);
    return 0;
}