#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)+3];
int cost[20][20];
int n,m,x,y,c;
int main()
{
    in>>n>>m;
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
        cost[i][j]=inf;
    for(int i=1;i<=m;++i)
        in>>x>>y>>c,
        cost[x][y]=c,
        rev[y].push_back(x);
    for(int i=0;i<n;++i)
        dp[i][0]=inf;
    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) if(mask&(1<<i))
    {
        dp[i][mask]=inf;
        for(int x=0;x<rev[i].size();++x) if(mask&(1<<rev[i][x]))
            dp[i][mask]=min(dp[i][mask],dp[rev[i][x]][mask^(1<<i)]+cost[rev[i][x]][i]);
    }
    int ans=inf;
    for(int i=0;i<rev[0].size();++i)
        ans=min(ans,dp[rev[0][i]][(1<<n)-1]+cost[rev[0][i]][0]);
    if(ans==inf)
        out<<"Nu exista solutie"<<'\n';
    else out<<ans<<'\n';
    return 0;
}