#include<fstream>
#include<vector>
#define maxn 20
#define maxconf 362150//(1<<18) = 262144
#define inf 200000008
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");

vector <int> a[maxn];//graful transpus
int i,j,k,n,m,x,y,cost_m,sol,nr;
int cost[maxn][maxn];
int c[maxconf][maxn];

int minim(int a,int b){
    if(a<b) return a;
    else return b;
}

int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
                      fi>>x>>y>>cost_m;
                      cost[x][y]=cost_m;
                      a[y].push_back(x);
                     }
    
    nr=(1<<n)-1; 
    
    for(i=0;i<=nr;i++)
      for(j=0;j<n;j++) c[i][j]=inf;
    
    c[1][0]=0;
    
    for(i=1;i<=nr;i++)
      for(j=0;j<n;j++)
        if(i&(1<<j))
           for(k=0;k<(int)a[j].size();k++)
             if(i&(1<<a[j][k]))
                c[i][j]=minim(c[i][j],c[i^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
    
    sol=inf;
    for(i=0;i<(int)a[0].size();i++)
      sol=minim(sol,c[nr][a[0][i]]+cost[a[0][i]][0]);   
    
    if(sol==inf) fo<<"Nu exista solutie";
    else fo<<sol;
    
    fi.close();
    fo.close();
    return 0;
}