#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

const int MAXN = 20;
const int MAXX = (1 << 18);
const int INF = 1e9;

int n, m;
int adj[MAXN][MAXN];
int dp[MAXX][MAXN];
 
void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            adj[i][j] = INF;
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a][b] = w;
    }
    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 i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                for(int k = 0; k < n; k++){
                    //for every path i if j and k are both present in it and there is an edge from 
                    //k to j, check dp[path without j] that ends in k then add cost from k to j
                    if((i & (1 << k)) && adj[k][j] != INF)
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + adj[k][j]);
                }
            }
        }
    }
    int ans = INF;
    for(int i = 1; i < n; i++){
        if(adj[i][0] != INF)
            ans = min(ans, dp[(1 << n) - 1][i] + adj[i][0]);
    }
    if(ans == INF)
        cout << "Nu exista solutie\n";
    else
        cout << ans << '\n';
}  
 
int main(){
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}