#include <bits/stdc++.h>
using namespace std ;
ifstream fin("hamilton.in") ;
ofstream fout("hamilton.out") ;
const int NMAX=18 ;
#define pb(x) push_back(x)
vector <int> g[NMAX] ;
vector <vector<int>> dp(1<<NMAX,vector <int> (NMAX,1e9)),cost(NMAX,vector <int> (NMAX,1e9)) ; ;
int n,m,x,y,t ;
int main()
{
    fin>>n>>m ;
    for(int i=1; i<=m; ++i) fin>>x>>y>>t,g[y].pb(x),cost[x][y]=t ;
    dp[1][0]=0 ;
    for(int mask=3; mask<(1LL<<n); mask+=2)
    {
        for(int nod=1; nod<n; ++nod)
        {
            if(mask&(1LL<<nod))
            {
                for(int it:g[nod]) dp[mask][nod]=min(dp[mask][nod],dp[mask^(1LL<<nod)][it]+cost[it][nod]) ;
            }
        }
    }
    int mn=1e9 ;
    for(int i=1; i<n; ++i) mn=min(mn,dp[(1LL<<n)-1][i]+cost[i][0]) ;
    if(mn==1e9) fout<<"Nu exista solutie" ;
    else fout<<mn ;
    return 0;
}