#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
 
const int nMAX = 18;
 
int n, m;
int dp[1 << nMAX][nMAX];
int gf[nMAX][nMAX];
 
int main()
{
   fin >> n >> m;
   for (int i = 1; i <= m; ++i)
   {
      int a, b, c;
      fin >> a >> b >> c;
      gf[a][b] = c;
   }
 
   fill(dp[2], dp[1 << nMAX], INT_MAX>>1);
 
   for (int mask = 1; mask < (1<<n); mask += 2)
      for (int i = 1; i < n; ++i)
         if (mask & (1<<i))
            for (int j = 0; j < n; ++j)
               if (gf[j][i] && (mask & (1<<j)))
                  dp[mask][i] = min(dp[mask][i], dp[mask - (1<<i)][j] + gf[j][i]);
 
   for (int i = 1; i < n; ++i)
      if (gf[i][0])
         dp[(1<<n)-1][0] = min(dp[(1<<n)-1][0], dp[(1<<n)-1][i] + gf[i][0]);
 
   if (dp[(1<<n)-1][0] == INT_MAX>>1)
      fout << "Nu exista solutie";
   else
      fout << dp[(1<<n)-1][0];
}