#include <cstdio>
#define maxv 1<<20
#define inf 0x3f3f3f3f
#include <algorithm>

using namespace std;

int N,M,a[18][18],c[maxv][20];

int part(int nod,int viz){
    if(c[viz][nod] == 0){
        c[viz][nod] = inf;
        if(viz == (1<<nod) + 1)
            c[viz][nod] = a[0][nod] ? a[0][nod] : inf;
        else
         for(int i = 1;i < N;++i)
            if(a[i][nod]>0 && ((viz>>i) & 1))
              c[viz][nod] = min(c[viz][nod],part(i,viz-(1<<nod))+a[i][nod]);
    }
    return c[viz][nod];
}

int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d ",&N,&M);
    int x,y,z;
    while(M--){
        scanf("%d %d %d ",&x,&y,&z);
        a[x][y] = z;
    }
    int rez = inf;
    for(x = 1;x < N;++x)
        if(a[x][0] > 0)rez = min(rez,a[x][0] + part(x,(1<<N)-1));
    if(rez == inf)printf("Nu exista solutie\n");
    else printf("%d\n",rez);
    return 0;
}