#include <fstream>
#define inf 1000001
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int c[1<<18+5][20],i,j,k,p,n,m,dim,cost[20][20],x,y,cst,mn;
int main()
{
    f>>n>>m;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
        cost[i][j]=inf;
    for(i=1;i<=m;i++) {f>>x>>y>>cst;cost[x][y]=cst;}
    dim=(1<<n)-1;
    for(i=0;i<=dim;i++)
        for(j=0;j<n;j++) c[i][j]=inf;
    c[1][0]=0;
    for(i=0;i<=dim;i++)
        for(j=0;j<n;j++)
            if(i&(1<<j))
            for(p=0;p<n;p++)
            if(cost[p][j]!=inf)
            {
                if(c[i^(1<<j)][p]+cost[p][j]<c[i][j]) c[i][j]=c[i^(1<<j)][p]+cost[p][j];
            }
    mn=inf;
    for(i=0;i<n;i++)
        if(cost[i][0]!=inf&&mn>c[dim][i]+cost[i][0])
        mn=c[dim][i]+cost[i][0];
    if(mn!=inf)g<<mn<<'\n';
    else g<<"Nu exista solutie";
    return 0;
}