#include <bits/stdc++.h>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int dim=262150,inf=1e9;

vector<int>adj[20];

int n,m,cost[20][20];
int memo[dim][20];

int dp(int stare,int last){
    if(memo[stare][last]==-1){
        int ans=inf;
        for(int i:adj[last]){
            if(stare&(1<<i)){
                int stare_noua=stare^(1<<last);
                if(stare_noua&1){
                    ans=min(ans,dp(stare_noua,i)+cost[i][last]);
                }
            }
        }
        memo[stare][last]=ans;
    }
    return memo[stare][last];
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        cost[x][y]=c;
        adj[y].push_back(x);
    }
    for(int i=0;i<=(1<<n)-1;i++){
        for(int j=0;j<n;j++){
            memo[i][j]=-1;
        }
    }
    memo[1][0]=0;
    int ans=inf;
    for(int i:adj[0]){
        ans=min(ans,dp((1<<n)-1,i)+cost[i][0]);
    }
    if(ans==inf){
        fout<<"Nu exista solutie";
    }else{
        fout<<ans;
    }
}