#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,x,y;
int cst[20][20],dp[263000][20];
vector<int>nod[20];
stack<tuple<int,int,int> >stk;
bool ap[263000][20];
int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    memset(cst,INF,sizeof cst);
    memset(dp,INF,sizeof dp);
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        fin>>cst[x][y];
        nod[y].push_back(x);
    }
    int ans=INF;
    dp[1][0]=0;
    for(int i=0;i<nod[0].size();i++)
        stk.push(make_tuple((1<<n)-1,nod[0][i],-1));
    while(!stk.empty())
    {
        int conf=get<0>(stk.top());
        int pos=get<1>(stk.top());
        int last=get<2>(stk.top());
        if(ap[conf][pos])
        {
            stk.pop();
            if(last==-1)
            {
                ans=min(ans,dp[conf][pos]+cst[pos][0]);
                continue;
            }
            dp[conf^(1<<last)][last]=min(dp[conf^(1<<last)][last],dp[conf][pos]+cst[pos][last]);
            continue;
        }
        ap[conf][pos]=true;
        for(int i=0;i<nod[pos].size();i++)
        {
            if(!(conf & (1<<nod[pos][i]))) continue;
            if(nod[pos][i]==0 && conf!=(1<<pos)+1) continue;
            stk.push(make_tuple(conf^(1<<pos),nod[pos][i],pos));
        }
    }
    if(ans==INF)
        fout<<"Nu exista solutie";
    else
        fout<<ans;
    return 0;
}