#include <bits/stdc++.h>
#define NMAX 18
#define PMAX 262150
#define INF 1000000000

using namespace std;

int N, M;
int cost[NMAX + 1][NMAX + 1];
int dp[PMAX + 1][NMAX + 1];

vector<int> G[NMAX + 1];

int ciclu( int mask, int last ) {
  if( dp[mask][last] == -1 ) {
    dp[mask][last] = INF;
    for( auto it : G[last] )
      if( mask & (1<<it) ) {
        if( it == 0 && mask != (1<<last) + 1 )
          continue;
        dp[mask][last] = min(dp[mask][last], ciclu(mask ^ (1<<last), it) + cost[it][last]);
      }
  }
  return dp[mask][last];
}

int main() {
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int i, j, x, y, val;
    fin>>N>>M;
    for( i = 0; i <= N; i ++ )
      for( j = 0; j <= N; j ++ )
        cost[i][j] = INF;

    for( i = 1; i <= M; i ++ ) {
      fin>>x>>y>>val;
      G[y].push_back(x);
      cost[x][y] = val;
    }

    int ans = INF;
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;

    for( auto it : G[0] )
      ans = min(ans, ciclu((1<<N)-1,it) + cost[it][0]);

    if( ans == INF )
      fout<<"Nu exista solutie";
    else
      fout<<ans;
    return 0;
}