# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>
# define inf 999999999
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
struct elem
{
    int y, cost;
}E;
vector <elem> v[50];
struct elem2
{
    int k, past;
}X;
queue <elem2> q;
int i,j,n,m,x,y,minn;
int dist[19][1<<19],drum[50][50];
void back()
{
    int i,k,next,past,cost;
    X.k=0; X.past=1;
    q.push(X);

    while (! q.empty())
    {
        X=q.front(); q.pop();
        k=X.k; past=X.past;
        if (past==(1<<n)-1)
        {
            if (drum[k][0]) minn=min(minn,dist[k][(1<<n)-1]+drum[k][0]);
        }
        for (i=0; i<v[k].size(); ++i)
        {
            next=v[k][i].y; cost=v[k][i].cost;
            if (((1<<next)&past)==0)
            {
                if (!dist[next][past+(1<<next)] || dist[next][past+(1<<next)]>dist[k][past]+cost)
                {
                    dist[next][past+(1<<next)]=dist[k][past]+cost;

                    X.k=next; X.past=past+(1<<next);
                    q.push(X);
                }
            }
        }
    }
}
int main ()
{
    f>>n>>m;
    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>E.cost;
        E.y=y; v[x].push_back(E);
        drum[x][y]=E.cost;
    }
    minn=inf;
    back();
    if (minn==inf) g<<"Nu exista solutie\n";
        else g<<minn<<"\n";
    return 0;
}