#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

#define MAX_N 19
#define MAX_C 1e6+1
#define INF 2e9

vector <int> gr[MAX_N];
int cost[MAX_N][MAX_N];
int dp[1<<MAX_N][MAX_N];

int main(){
    FILE *fin, *fout;
    int n,m,x,y,c,i,j,ans;
    fin=fopen("hamilton.in","r");
    fout=fopen("hamilton.out","w");
    fscanf(fin,"%d%d",&n,&m);

    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        cost[i][j]=MAX_C;
      }
    }

    for(i=0;i<m;i++){
      fscanf(fin,"%d%d%d",&x,&y,&c);
      gr[x].push_back(y);
      cost[x][y]=c;
    }

    for(i=0;i<(1<<n);i++){
      for(j=0;j<n;j++){
        dp[i][j]=INF;
      }
    }

    dp[1][0]=0;
    for(i=0;i<(1<<n);i++){
      for(j=0;j<n;j++){
        if((i&(1<<j))){
          for(int nei:gr[j]){
            if((i&(1<<nei)) && dp[i][nei]>cost[j][nei]+dp[i^(1<<nei)][j]){
              dp[i][nei]=cost[j][nei]+dp[i^(1<<nei)][j];
            }
          }
        }
      }
    }

    ans=INF;
    for(i=1;i<n;i++){
      if(ans>dp[(1<<n)-1][i]+cost[i][0] && cost[i][0]!=MAX_C){
        ans=dp[(1<<n)-1][i]+cost[i][0];
      }
    }


    if(ans==INF){
      fprintf(fout,"Nu exista solutie");
    }else{
      fprintf(fout,"%d",ans);
    }



    fclose(fin);
    fclose(fout);
    return 0;
}