#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 18;
int dp[(1 << NMAX)][NMAX];

struct nod{
    
    int to, cost;
    
};

vector<nod> adj[NMAX];

//dp[i][j] costul minim al ciclului de configuratie i si ult nod adaugat j

int main()
{
    
    int n, m;
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        
    }
    
    for(int i=0; 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 config=0; config< (1 << n); config++){
        
        for(int i=0; i<n; i++){
            
            if(dp[config][i] != 2e9){
                
                //verifc daca urm nod nu e deja in config
                for(nod next : adj[i]){
                    
                    if((config & (1 << next.to)) == 0)
                        dp[config | (1 << next.to)][next.to] = min(dp[config | (1 << next.to)][next.to], dp[config][i] + next.cost);
                    
                }
                
            }
            
        }
        
    }
    
    int mn = 2e9;
    
    for(int i=1; i<n; i++){
        
        
        for(nod next : adj[i])
            if(next.to == 0)
                mn = min(mn, dp[(1 << n) - 1][i] + next.cost);
                
      
    }
    
    if(mn == 2e9)
        g << "Nu exista solutie";
        
    else g << mn;
    
    

    return 0;
}