#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#define x first
#define y second
#include<stack>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,dp[20][(1<<18)+5],a,b,c,p[20],t;
vector<pair<int,int> >x[20];;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        x[a].push_back({b,c});
        if(b==0)
            p[a]=c;
    }
    dp[0][1]=1;
    for(int h=1;h<(1<<n);h++)
        if((h&(1<<0)))
    {
        for(int i=0;i<n;i++)
            if((h&(1<<i)))
                if(dp[i][h])
                    for(auto j:x[i])
                        if(!(h&(1<<j.x)))
                            if(dp[j.x][(h|(1<<j.x))]==0||dp[j.x][(h|(1<<j.x))]>dp[i][h]+j.y)
                                dp[j.x][(h|(1<<j.x))]=dp[i][h]+j.y;
    }
    if(n==1)
    {
        fout<<0;
        return 0;
    }
    int mi=(1<<28);
    for(int i=1;i<=n;i++)
        if(dp[i][(1<<n)-1]&&p[i])
        {
            mi=min(mi,dp[i][(1<<n)-1]+p[i]);
            t=1;
        }
    mi--;
    if(!t)
    {
        fout<<"Nu exista solutie";
        return 0;
    }
    fout<<mi;
}