#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxp=1000000000;
int n,m,i,j,k,d[262145][20],c[20][20],sol=maxp;
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        c[i][j]=maxp;
    for(i=1;i<=m;i++)
        scanf("%d%d",&j,&k), scanf("%d",&c[j][k]);
    for(i=1;i<(1<<n);i++)
        for(j=1;j<n;j++)
        d[i][j]=maxp;
    d[1][0]=0;
    for(i=1;i<(1<<n);i++)
        for(j=0;j<n;j++)
        {
        if(i!=1&&j==0)continue;
        if(d[i][j]==maxp)continue;
            for(k=1;k<n;k++)
                if(c[j][k]>0&&(i&(1<<k)!=0))
                    d[i^(1<<k)][k]=min(d[i][j]+c[j][k],d[i^(1<<k)][k]);
        }
    for(i=1;i<n;i++)
        if(sol>d[(1<<n)-1][i]+c[i][0]&&c[i][0]>0) sol=d[(1<<n)-1][i]+c[i][0];
    if(sol==maxp)
        printf("Nu exista solutie");
    else
        printf("%d",sol);
    return 0;
}