#include <cstdio>
#include <vector>
#define inf 0x3f3f3f3f
#include <algorithm>

using namespace std;

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

int calc(int,int);

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);
        G[y].push_back(x);
        cost[x][y] = z;
    }
    int S = inf;
    for(x = 0;x <= (1<<N);++x){
        for(y = 0;y <= N;++y)C[x][y] = -1;
    }
    C[1][0] = 0;
    for(size_t i = 0;i < G[0].size();++i)S = min(S,calc((1<<N)-1,G[0][i])+cost[G[0][i]][0]);
    if(S == inf)puts("Nu exista solutie\n");
    else printf("%d\n",S);
    return 0;
}
int calc(int conf,int nod){
    if(C[conf][nod] == -1){
        C[conf][nod] = inf;
        for(size_t i = 0;i < G[nod].size();++i)
            if(conf & (1<<G[nod][i])){
                    if(G[nod][i]!=0 || (conf == (1<<nod)+1))C[conf][nod] = min(C[conf][nod],calc(conf ^ (1<<nod),G[nod][i]) + cost[G[nod][i]][nod]);
                }
    }
    return C[conf][nod];
}