#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int maxn=20;
vector<int>adj[maxn];
int d[(1<<maxn)][maxn];
int n,m;
int cost[maxn][maxn];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        adj[y].push_back(x);
        cost[x][y]=c;
    }
    d[0][0]=1;
    for(int mask=1;mask<(1<<n);mask++){
        for(int end=0;end<n;end++){
            if((mask&(1<<end))){
                for(auto vecin:adj[end]){
                    if(d[(mask-(1<<end))][vecin]){
                        if(d[mask][end]==0) d[mask][end]=1e9;
                        d[mask][end]=min(d[mask][end],d[(mask^(1<<end))][vecin]+cost[vecin][end]);
                    }
                }
            }
        }
    }
    if(d[(1<<n)-1][0]==0) cout<<"Nu exista solutie";
    else cout<<d[(1<<n)-1][0]-1;
    return 0;
}