#include<cstdio>
#include<vector>
#include<utility>
#define first V
#define second C
#define N 17
#define M 1<<17
#define oo 20000000
using namespace std;
int n,m,x,y,c,a[M][N],v[N+1][N+1],sol=oo,p,q;
int main()
{
    int i,j,k;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        v[x][y]=c;
    }
    for(i=0;i<n-1;i++)
        if(v[n-1][i])a[1<<i][i]=v[n-1][i];
    int m=(1<<(n-1))-1;
    for(i=1;i<m;i++)
        for(j=0;j<n-1;j++)
            if(a[i][j])
                for(k=0;k<n-1;k++)
                {
                    if(!v[j][k])continue;
                    if(i&(1<<k))continue;
                    p=i|(1<<k);
                    q=a[i][j]+v[j][k];
                    if(!a[p][k]){a[p][k]=q;continue;}
                    if(q<a[p][k])a[p][k]=q;
                }
    for(i=0;i<n-1;i++)
        if(a[m][i]&&v[i][n-1])
            sol=min(sol,a[m][i]+v[i][n-1]);
    if(sol==oo)
        printf("Nu exista solutie");
    else
        printf("%d", sol);
    return 0;
}