#include <cstdio>
#define INF 0x3f3f3f3f
#include <vector>
#include <cstring>
#include <algorithm>
#define maxv 262150

using namespace std;

int N,M,COST[20][20],Rez=INF,C[maxv][20];
vector <int> G[20];

int Part(int arg2,int arg3){
    if(C[arg2][arg3] == -1){
        C[arg2][arg3] = INF;
        for(size_t i = 0;i < G[arg3].size();++i){  ///parcurg nodurile care arata spre ultimul nod din lant
            if(arg2 & (1 << G[arg3][i])){ ///doar cele care apartin lantului vor fi alese
                if(G[arg3][i] == 0 && arg2 != (1 << arg3) + 1)continue;  ///nodul 1 trebuie scos ultimul
                C[arg2][arg3] = min(C[arg2][arg3],Part(arg2^(1<<arg3),G[arg3][i]) + COST[G[arg3][i]][arg3]);
            }
        }
    }
    return C[arg2][arg3];
}
int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int i,j,k;
    scanf("%d %d ",&N,&M);
    for(i=0;i<N;++i)
        for(j=0;j<N;++j)COST[i][j] = INF;
    while(M--){
        scanf("%d %d %d ",&i,&j,&k);
        G[j].push_back(i);  ///retin arcul invers;
        COST[i][j] = k;
    }
    memset(C,-1,sizeof(C));
    C[1][0] = 0;
    ///Es ist unmoglich ohne Recursivitat;

    for(size_t it = 0;it < G[0].size();++it)
        Rez = min(Rez,Part((1<<N)-1,G[0][it]) + COST[G[0][it]][0]);

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