#include <cstdio>
#include <vector>
#define maxx 1<<18
#define inf 0x3f3f3f3f
#include <cstring>
#include <algorithm>

using namespace std;

int N,M;
int C[maxx][20],cost[20][20];
vector <int> G[maxx];


int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d ",&N,&M);

    memset(cost,inf,sizeof(cost));

    while(M--){
        int x,y,z;
        scanf("%d %d %d ",&x,&y,&z);
        G[y].push_back(x);
        cost[x][y] = z;
    }

    int S = inf;
    memset(C,inf,sizeof(C));
    C[1][0] = 0;

    for(int conf = 0;conf < (1<<N);++conf)
        for(int i = 0;i < N;++i)
           if(conf & (1<<i))
             for(size_t j = 0;j < G[i].size();++j)
                if(conf & (1<<G[i][j]))
                C[conf][i] = min(C[conf][i],C[conf ^ (1<<i)][G[i][j]] + cost[G[i][j]][i]);

    for(int i = 0;i < G[0].size();++i)
        S = min(S,C[(1<<N)-1][G[0][i]] + cost[G[0][i]][0]);

     if(S != inf)printf("%d\n",S);
     else printf("Nu exista solutie\n");
    return 0;
}