#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,i,j,cost[20][20],oo=1000000000,a[(1<<18)][19],x,y,c,k;

vector < int > G[20];

int main()
{
    fin>>n>>m;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<=n;j++)
            a[i][j]=oo;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
            cost[i][j]=oo;
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(y);
        cost[x][y]=c;
    }
    a[1][0]=0;
    for(k=0;k<(1<<n);k++)
    {
        for(j=0;j<n;j++)
        {
            if((k & (1<<j))!=0)
            {
                for(auto urm : G[j])
                {
                    if((k & (1<<urm))==0)
                    {
                        a[k | (1<<urm)][urm]=min(a[k][j]+cost[j][urm],a[k | (1<<urm)][urm]);
                    }
                }
            }
        }
    }
    int r=oo;
    for(i=1;i<n;i++)
    {
        if(cost[i][0]!=oo)
        r=min(r,a[(1<<n)-1][i]+cost[i][0]);
    }
    if(r==oo)
        fout<<"Nu exista solutie";
    else
        fout<<r;
    return 0;
}