#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
//#define int long long
//#define int short
using namespace std;

const int nmax = 18;
const int inf = 1e9;

int n, m, dp[(1 << nmax) + 1][nmax + 1];
vector<pair<int, int>> adj[nmax + 5];

int ciclu(int startnode){
    for (int mask = 0; mask < (1 << n); mask++){
        for (int i = 0; i < n; i++){
            dp[mask][i] = inf;
        }
    }
    dp[(1 << startnode)][startnode] = 0;
    for (int mask = 1; mask < (1 << n); mask++){
        for (int bit = 0; bit < n; bit++){
            if (dp[mask][bit] == inf){
                continue;
            }
            for (auto& [i, c] : adj[bit]){
                if (!(mask & (1 << i))){
                    int newmask = mask | (1 << i);
                    dp[newmask][i] = min(dp[newmask][i], dp[mask][bit] + c);
                }
            }
        }
    }
    int rez = inf;
    for (int i = 0; i < n; i++){
        for (auto& [j, c] : adj[i]){
            if (j == startnode){
                rez = min(rez, dp[(1 << n) - 1][i] + c);
            }
        }
    }
    return rez;
}

int getans(){
    int rez = inf;
    for (int i = 0; i < n; i++){
        rez = min(rez, ciclu(i));
    }
    return rez;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    cin>>n>>m;
    while (m--){
        int u, v, c;
        cin>>u>>v>>c;
        adj[u].push_back({v, c});
    }
    int idk = getans();
    if (idk == inf){
        cout<<"Nu exista solutie";
        return 0;
    }
    cout<<idk;
}