#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");
const int INF=2e9;
vector <pair<int,int>> L[18];
int D[18][(1<<18)];
int V[18];
int n,m,i,stare,sol,x,y,cost;
int main()
{
    fin>>n>>m;
    for(i=0;i<n;i++)
    {
        V[i]=INF;
        for(stare=1;stare<(1<<n);stare+=2)
            D[i][stare]=INF;
    }
    const int visit_all=(1<<n)-1;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        L[x].push_back({y,cost});
        if(y==0)
            V[x]=cost;
    }
    sol=INF;
    D[0][1]=0;
    for(stare=1;stare<(1<<n);stare+=2)
    {
        for(i=0;i<n;i++)
            if(D[i][stare]!=INF)
            {
                for(auto j:L[i])
                {
                    if(!(stare&(1<<j.first)))
                    {
                        int next_stare=stare+(1<<j.first);
                        D[j.first][next_stare]=min(D[j.first][next_stare],D[i][stare]+j.second);
                    }
                }
            }
    }
    for(i=1;i<n;i++)
    {
        if(V[i]!=INF&&D[i][visit_all]!=INF)
            sol=min(sol,D[i][visit_all]+V[i]);
    }
    if(sol!=INF)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    return 0;
}