#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int MAX = 18 * 17;
const int INF = INT_MAX / 2;
int N, M;
vector<int>G[MAX + 3];
int x, y, c;
int cost[20][20];
int dp[1 << 18 + 3][20];
int main() {    
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> x >> y >> c;
        G[y].push_back(x);
        cost[x][y] = c;
    }
    for(int i = 0; i <= (1 << N); i++) {
        for(int j = 0; j <= N; j++) {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    for(int mask = 1; mask <= (1 << N); mask++) {
        for(int j = 1; j <= N; j++) {
            if(mask & (1 << j)) {
                for(auto k : G[j]) {
                    if(mask & (1 << k)) {
                        dp[mask][j] = min(dp[mask][j], dp[mask - (1 << j)][k] + cost[k][j]);
                    }
                }
            }
        }
    }
    int sol = INF;
    for(auto k : G[0]) {
        sol = min(sol, dp[(1 << N) - 1][k] + cost[k][0]);
    }
    if(sol == INF) cout << "Nu exista solutie";
    else cout << sol;
}