#include <bits/stdc++.h>
using namespace std;
//Soltan Cristian
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
string __fname = "hamilton"; 
ifstream in (__fname + ".in"); 
ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
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;
    // cout << "a\n";
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
    }
    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++){
                    //check if k is included in i and check if there is edge between the two 
                    //and update
                    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()
{   
    // ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed  << setprecision(10); 
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    return 0;
}