#include <bits/stdc++.h>
using namespace std;

int main() {

    freopen("hamiltonian.in", "r", stdin);
    freopen("hamiltonian.out", "w", stdout);
    cin.tie(0); 
    ios_base::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>>G(N + 3);

    for(int i = 1; i <= M; i++) {
        int x, y, c; cin >> x >> y >> c;
        // G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    vector<vector<int>>dp((1 << N) + 2, vector<int>(N + 2, 1e9));

    dp[1][0] = 0;

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            for(auto [v, cost] : G[j]) {
                if((1 << j) & i) {  
                    // cerr << dp[i - (1 << v)][v] + cost << ' ' << i - (1 << v)   << ' ' << v << '\n';
                    dp[i][j] = min(dp[i][j], dp[i - (1 << j)][v] + cost);
                }
            }
            // cout << dp[i][j] << ' ';
        }
        // cout << '\n';
    }

    int ans = 1e9;
    for(auto [i, cst] : G[0]) {
        ans = min(ans, dp[(1 << N) - 1][i] + cst);
    }
    if(ans == 1e9) cout << "Nu exista solutie";
    else cout << ans;

}