#include<fstream>
#include<vector>
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int INF = 1e9;

vector<pair<int, int>> v[19]; /// nod, cost
int dp[19][1<<19], v1[18][18];

int main()
{
   int n, m;
   cin>>n>>m;
   for(int i=1; i<=m; i++)
   {
      int x, y, c;
      cin>>x>>y>>c;
      v[x].push_back({y, c});
      v1[x][y] = c;
   }

   for(int mask=1; mask < 1<<18; mask++)
      for(int nod=0; nod <= n; nod++)
         dp[nod][mask] = INF;

   dp[0][1] = 0;
   int minim = INF;
   for(int mask=1; mask < 1<<18; mask++)
      for(int nod=0; nod <= n; nod++)
         if(dp[nod][mask] != INF)
         {
            //cout<<nod<<" "<<mask<<" "<<dp[nod][mask]<<'\n';
            if(mask == (1<<n)-1 && v1[nod][0])
               minim = min(minim, dp[nod][mask] + v1[nod][0]);
            for(auto x : v[nod])
            {
               int vecin = x.first;
               int cost = x.second;
               if(!(mask & (1<<vecin)))
               {
                  dp[vecin][mask ^ (1<<vecin)] = min(dp[vecin][mask ^ (1<<vecin)], dp[nod][mask] + cost);
               }
            }
         }
   if(minim != INF)
      cout<<minim;
   else
      cout<<"Nu exista solutie";
   return 0;
}