#include <bits/stdc++.h>

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

vector<pair<int, int>> adj[18];

int n, m;

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

int muchie[18][18];

int main()
{
    
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        // adj[y].push_back({x, cost});
        
        muchie[x][y] = cost;
        // muchie[y][x] = cost;
        
        
    }
    
    
    
    for(int i=1; i<(1 << n); i++)
        for(int j=0; j<n; j++)
            dp[i][j] = 2e9;
            
    for(int i=0; i<n; i++)
        dp[(1 << i)][i] = 0;
        
 
    for(int i=0; i<(1 << n); i++){
        
        for(int j=0; j<n; j++){
            
            if(dp[i][j] == 2e9){
                
                continue;
                
            }
            
            for(auto next : adj[j]){
                int nod_nou = (1 << next.first);
            
                if((i & nod_nou) == 0)
                    dp[i + nod_nou][next.first] = min(dp[i + nod_nou][next.first], next.second + dp[i][j]);
            
            }
        }
            
    }
    
    int mn = 2e9;
    
    for(int i=0; i<n; i++){
        
        for(auto next : adj[i])
            if(next.first == 0)
                mn = min(mn, dp[(1 << n) - 1][i] + next.second);
            
        //cout << dp[(1 << n) - 1][i] << endl;
            
    }
        
    
    if(mn == 2e9)
        g << "Nu exista solutie";
    else
    
    g << mn;
        

    return 0;
}