#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cstring>

using namespace std;

int n, m;
vector<pair<int, int> > graph[22];

void read(){
  freopen("hamilton.in", "r", stdin);

  scanf("%d%d", &n, &m);

  for(int i = 1; i <= m; ++i){
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    graph[x].push_back(make_pair(y, c));
  }
}

int ans, dp[19][1<<18];

void solve(){
  memset(dp, 1337, sizeof(dp));

  dp[0][1] = 0;

  int lim = 1 << n;
  for(int j = 1; j < lim; ++j)
    for(int i = 0; i < n; ++i)  if((1 << i) & j)
      for(int k = 0; k < graph[i].size(); ++k)
        if(j & (1 << graph[i][k].first));
        else
          dp[graph[i][k].first][j + (1 << graph[i][k].first)] = min (dp[graph[i][k].first][j + (1 <<
                                                                      graph[i][k].first)], dp[i][j] +
                                                                      graph[i][k].second);

  ans = 2000000000;

  for(int i = 1; i < n; ++i)
    for(int j = 0; j < graph[i].size(); ++j)
      if(graph[i][j].first == 0)
        ans = min(ans, dp[i][(1 << n) - 1] + graph[i][j].second);
}

void write(){
  freopen("hamilton.out", "w", stdout);

  printf("%d", ans);
}

int main(){
  read();
  solve();
  write();

  return 0;
}