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

const int nmax = 18;

int dp[(1<<nmax)][nmax];

int adj[nmax][nmax];

signed main(){
    
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        //vecini[a].push_back(b);
        adj[a][b] = c;
    }
    for(int i = 0; i < (1<<n); i++){
        for(int j = 0; j < n; j++){
            dp[i][j] = 1e9;
        }
    }
    dp[1][0] = 0;
    for(int mask = 1; mask < (1<<n); mask++){
        for(int b = 0; b < n; b++){
            if((mask & (1<<b)) == 0) continue;
            for(int b2 = 0; b2 < n; b2++){
                if(adj[b][b2] == 0)continue;
                if(mask & (1<<b2)) continue;
                dp[(mask | (1<<b2))][b2] = min(dp[(mask | (1<<b2))][b2], dp[mask][b] + adj[b][b2]);
            }
        }
    }
    int ans = 1e9;
    for(int i = 0; i < n; i++){
        if(adj[i][0] != 0)
            ans = min(ans, dp[(1<<n) - 1][i] + adj[i][0]);
    }
    if(ans == 1e9){
        cout << "Nu exista solutie\n";
    }
    else
        cout << ans << '\n';
}