#include <fstream>
#define INF 100000000
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int N, M, dist[20][20], a, b, c, memo[1 << 18][20];

int solve( int mask, int x)
{
  if(mask == (1 << N) - 1)
  {
    if(dist[x][0])
      return dist[x][0];
    else return INF;
  }

  if(memo[mask][x] != -1)
    return memo[mask][x];

  int cost_min = INF;
  for(int k = 0; k < N; k++)
  {
    if(!(mask & (1 << k)) and dist[x][k]){
      int cost = dist[x][k] + solve( mask | (1 << k), k);
      cost_min = min( cost_min, cost );
    }
  }
  memo[mask][x] = cost_min;
  return cost_min;
}

int main()
{
  cin >> N >> M;

  for(int i = 1; i <= M; i++)
  {
    cin >> a >> b >> c;
    dist[a][b] = c;
  }

  for(int k = 0; k < (1<<N); k++)
    for(int i = 0; i < N; i++)
      memo[k][i] = -1;

  int ans = INF;
  for(int k = 0; k < N; k++)
  {
    if(dist[0][k] != INF)
    {
      int cost_curr = dist[0][k] + solve( 1 << k, k);
      ans = min ( ans, cost_curr );
    }
  }
  cout << ans;
  return 0;
}