#include <bits/stdc++.h>
using namespace std;
const int MAXN = 18;
const int INF = 1e9;

ifstream fin( "hamilton.in" );
ofstream fout( "hamilton.out" );

int dp[MAXN][(1<<MAXN)];
int mat[MAXN][MAXN];
int main() {
  int n, m, i, j, a, b, cost, mask, ans;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b >> cost;
    mat[a][b] = cost;
  }
  for( mask = 0; mask < ( 1 << n ); mask++ ) {
    for( i = 0; i < n; i++ )
      dp[i][mask] = INF;
  }
  for( i = 0; i < n; i++ ) {
    dp[i][1<<i] = 0;
  }
  for( mask = 0; mask < ( 1 << n ); mask++ ) {
    for( i = 0; i < n; i++ ) {
      if( ( mask & ( 1 << i ) ) ) { // nodul i e in masca
        for( j = 0; j < n; j++ ) {
          if( ( mask & ( 1 << j ) ) && mat[i][j] > 0 )  // nodul j e in masca si exista muchie i-j
            dp[j][mask] = min( dp[j][mask], dp[i][mask-(1<<j)] + mat[i][j] );
        }
      }
    }
  }
  /*for( mask = 0; mask < ( 1 << n ); mask++ ) {
    for( i = 0; i < n; i++ )
      cout << dp[i][mask] << " ";
    cout << "\n";
  }*/
  ans = INF;
  for( i = 0; i < n; i++ ) {
    if( mat[i][0] > 0 )
      ans = min( ans, dp[i][(1<<n)-1] + mat[i][0] );
  }
  fout << ans;
  return 0;
}