#include <bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int inf=1e9+7;
vector<int> rev[20];
int dp[20][(1<<18)];
int cost[20][20];
int n,m,x,y,c;
int main()
{
    in>>n>>m;
    for(int i=0;i<n;++i)
        cost[i][i]=inf;
    for(int i=1;i<=m;++i)
        in>>x>>y>>c,
        cost[x][y]=c,
        rev[y].push_back(x);
    dp[0][1]=0;
    for(int i=1;i<n;++i)
        dp[i][1]=inf;
    for(int mask=2;mask<(1<<n);++mask)
    for(int i=0;i<n;++i)
    {
        dp[i][mask]=inf;
        if(mask&(1<<i)) for(int x:rev[i])
            dp[i][mask]=min(dp[i][mask],dp[x][mask^(1<<i)]+cost[x][i]);
    }
    int ans=inf;
    for(int i:rev[0])
        ans=min(ans,dp[i][(1<<n)-1]+cost[i][0]);
    if(ans==inf)
        out<<"Nu exista solutie"<<'\n';
    else out<<ans<<'\n';
    return 0;
}