#include <bits/stdc++.h>
#define fi first 
#define se second 
#define int long long
using namespace std;

signed main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> a(n + 1);
    
    for(int i = 1; i <= m; i ++) {
        int x, y, z; cin >> x >> y >> z;
        a[x].push_back({y, z});
    }

    vector<vector<int>> dp((1 << n), vector<int>(n, 1e9));
    dp[1][0] = 0;

    for(int mask = 1; mask < (1 << n); mask ++) {
        for(int i = 0; i < n; i ++) {
            if((mask & (1 << i)) == 0)
                continue;
            for(auto j : a[i]) {
                if((mask & (1 << j.fi)) != 0)
                    continue;
                dp[mask ^ (1 << j.fi)][j.fi] = min(dp[mask ^ (1 << j.fi)][j.fi], dp[mask][i] + j.se);
            }
        }
    }

    int ans = 1e9;

    for(int i = 1; i < n; i ++) {
        int z = 0;
        for(auto j : a[i]) {
            if(j.fi == 0)
                z = j.se;
        }
        if(!z)
            continue;
        ans = min(ans, dp[(1 << n) - 1][i] + z);
    }

    if(ans >= 1e9)
        cout << "Nu exista solutie";
    else
        cout << ans;
}