#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f3

long long n,m,a,b,c;
long long path[25][25];
long long dp[1<<19][19];

int main(void){
 ifstream cin("hamilton.in");
 ofstream cout("hamilton.out");
 memset(dp,0,sizeof dp);
 memset(path,0,sizeof path);
 cin>>n>>m;
 while(m--){
     cin>>a>>b>>c;
     path[a][b] = c;
 }
 for (int i=0;i<n;++i)
  for (int j=0;j<n;++j)
   if (!path[i][j])
    path[i][j] = inf;

long long ans = inf;
 for (int mask = 0; mask<(1<<n); ++mask)
     for (int i=0; i<n; ++i)
        if (mask&(1<<i))
            for (int j=0; j<n; ++j){
                int Nmask = mask | (1<<j);
                if (path[i][j]>0) {
                   if (!(mask&(1<<j))) {
                       if (dp[Nmask][j]==0) dp[Nmask][j] = dp[mask][i] + path[i][j];
                                       else dp[Nmask][j] = min(dp[Nmask][j],dp[mask][i] + path[i][j]);
                   if (__builtin_popcount(Nmask)==n && path[j][0]>0) ans = min(ans,dp[Nmask][j]+ path[j][0]);
                   }
                }
                else {
                      if (!(mask&(1<<j))) dp[mask|(1<<j)][j] = inf;
               }
            }
 if (ans!=inf) cout<<ans;
       else cout<<"Nu exista solutie";
return 0;
}