#include <bits/stdc++.h>
#define maxN 20
#define inf 1000000002

FILE *fin  = freopen("hamilton.in", "r", stdin);
FILE *fout = freopen("hamilton.out", "w", stdout);

using namespace std;
int N, M;
int cost[maxN][maxN];
int dp[(1 << maxN)][maxN];
vector <int> G[maxN];

void init(){
    for(int i = 0; i < (1 << N); ++ i)
        for(int j = 0; j < N; ++ j)
            dp[i][j] = inf;
    for(int i = 0; i < N; ++ i)
        dp[1 << i][i] = 0;
    //dp[1][0] = 0;
}

void read(){
    for(int i = 1; i <= M; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        scanf("%d", &cost[x][y]);
        G[y].push_back(x); /// daddy issues
    }
}

int main(){
    scanf("%d %d", &N, &M);
    init();
    read();
    for(int i = 1; i < (1 << N); ++ i)
        for(int j = 1; j < N; ++ j)
            if(i & (1 << j)){
                for(int dady : G[j])
                    if(i & (1 << dady))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][dady] + cost[dady][j]);
            }
    int sol = inf;
    for(int dady : G[0])
        sol = min(sol, dp[(1 << N) - 1][dady] + cost[dady][0]);
    if(sol == inf)
        printf("Nu exista solutie\n");
    else printf("%d\n", sol);
    return 0;
}