#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x)) 

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#endif

template<typename T>
bool ckmax(T &a, T b) {
   return a < b ? a = b, true : false;
}
template<typename T>
bool ckmin(T &a, T b) {
   return a > b ? a = b, true : false;
}

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 18;
const int INF = 1e9+5;

int n, m;
int dp[NMAX][1 << NMAX];
int cost[NMAX][NMAX];

void read() {
   fin >> n >> m;

   for (int i = 0; i < n; i++) {
      fill(cost[i], cost[i] + n, INF);
   }

   for (int i = 0, x, y, c; i < m; i++) {
      fin >> x >> y >> c;
      cost[x][y] = c;
   }
}

int solve() {
   for (int i = 0; i < n; i++) {
      fill(dp[i], dp[i] + (1 << n), INF);
   }
   dp[0][1] = 0;

   for (int m = 0; m < 1 << (n - 1); m++) {
      int mask = (m << 1) | 1;
      for (int i = 0; i < n; i++) {
         if ((mask >> i) & 1) {
            for (int j = 1; j < n; j++) {
               if (!((mask >> j) & 1))
                  ckmin(dp[j][mask | (1 << j)], dp[i][mask] + cost[i][j]);
            }
         }
      }
   }

   int ans = INF;
   for (int i = 1; i < n; i++) {
      ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
   }

   return ans;
}

signed main() {
   read();
   fout << solve() << endl;
   return 0;
}