/**
template <size_t S>
constexpr bool ls(const char a[S], const char b[S]) {
    for (int i = 0; i < S; ++i) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false;
}

static_assert(ls<8>(__TIME__, "18:50:00") || ls<8>("20:15:00, __TIME__)", "((");
**/
#include <bits/stdc++.h>

using namespace std;

const int N=18;

int n,m;
int dp[(1<<N)][N];
int cost[N][N];
vector<int>g[N];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[y].push_back(x);
        cost[x][y]=z;
    }
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=(int)1e9;
        }
    }
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                for(auto &k:g[j])
                {
                    if(i&(1<<k))
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+cost[k][j]);
                    }
                }
            }

        }
    }

    int ans=(int)1e9;
    for(auto &it:g[0])
    {
        ans=min(ans,dp[(1<<n)-1][it]+cost[it][0]);
    }
    if(ans==(int)1e9)
    {
        cout<<"Nu exista solutie\n";
    }
    else
    {
        cout<<ans<<"\n";
    }
    return 0;
}