#include<cstdio>
#include<vector>
#include <iostream>
#define iN "hamilton.in","r",stdin
#define ouT "hamilton.out","w",stdout
#define nmax 21
#define kmax 1<<19
#define INF 9999999
using namespace std;
vector<int>G[nmax];
int n,m,dp[kmax][nmax],cost[nmax][nmax];
inline void solve(){
 int i,j,q,best;
 for(i=0;i<(1<<n);i++)
    for(j=0;j<= n; j++)
     dp[i][j]=INF;
  dp[1][0]=0;
  for(i=0;i <(1<<n);i++)
    for(j=0;j<=n;j++)
     for(q=0;q<G[j].size();q++){
         if(dp[i][G[j][q]]!=INF){
            dp[i^(1<<j)][j]=min(dp[i^(1<<j)][j],dp[i][G[j][q]]+cost[G[j][q]][j]);
            }
    }
    best=INF;
    for(i=0;i<G[0].size();i++)
        if(dp[((1<<n)-1)][G[0][i]]+cost[G[0][i]][0]< best) best=dp[((1<<n)-1)][G[0][i]]+cost[G[0][i]][0];
     if(best == INF) cout << "Nu exista solutie\n";
     else
    cout<<best<<'\n';
}
int main(){
    int x,y,i,c;
    freopen(iN);
    freopen(ouT);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&c);
        G[y].push_back(x);
        cost[x][y]=c;
    }
    solve();
    return 0;
}