#include <stdio.h>
using namespace std;
int graf[19][19];
int a[1<<18][19];
int min(int a, int b)
{
    if(a<b) return a;
    return b;
}
const int inf=1000000000;
int n, m, x, y, c;
int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=0; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        graf[x][y]=c;
    }
    for(int i=1; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            a[i][j]=inf;
    a[1][0]=0;
    for(int i=1; i<1<<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i&(1<<j)!=0)
                   {
                       for(int k=0; k<n; k++)
                       {
                           if((i^(1<<j))&(1<<k) and graf[k][j]!=0)
                           {
                               a[i][j]=min(a[i][j],a[i ^ (1<<j)][k]+graf[k][j]);
                           }
                       }
                   }
            }
        }
    int minim=inf;
    for(int nod=1; nod<n; nod++)
    {
        if(a[(1<<n)-1][nod]+graf[nod][0]<minim and graf[nod][0]!=0)
            minim=a[(1<<n)-1][nod]+graf[nod][0];
    }
    if(minim==inf){printf("Nu exista solutie");return 0;}
    printf("%d", minim);
    return 0;
}