#include <bits/stdc++.h>
#define oo 20000000
using namespace std;
string z = "hamilton.";

ifstream f(z+"in");
ofstream g(z+"out");

int i,j,x,y,p,n,m,c[20][20],d[1<<18][20],r=oo;
vector<int> v[20];

int ham(int mask,int ep)
{
    if (d[mask][ep]==-1)
    {
        d[mask][ep]=oo;
        for (int i=0;i<v[ep].size();++i)
        {
            int x = v[ep][i];
            if (!x && (1<<ep)+1!=mask)continue;
            if (mask & (1<<x))
            {
                d[mask][ep]=min(ham(mask^(1<<ep),x)+c[x][ep],d[mask][ep]);
            }
        }
    }
    return d[mask][ep];
}

int main()
{
    f>>n>>m;
    for(i=0;i<=n;++i)for(j=0;j<=n;++j)c[i][j]=oo;
    memset(d,-1,sizeof(d));
    while(m--)
    {
        f>>x>>y>>p;
        c[x][y]=p;
        v[y].push_back(x);
    }
    d[1][0]=0;
    for(i=1;i<=n;++i)if (c[i][0]!=oo)
        r=min(r,ham((1<<n)-1,i)+c[i][0]);
    if (r == oo)
        g<<"Nu exista solutie";
    else g<<r;




    return 0;
}