#include<fstream>
#include<vector>
using namespace std;
#define inf 100000000
#define maxn 19
#define maxx 262150
int c[maxx][maxn],cost[maxn][maxn],n,m,x,y,rez;
vector <int> A[maxn];

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++)
      for(int j=0; j<n; j++)
        cost[i][j]=inf;
    rez=1<<n;
    for(int i=0; i<rez; i++)
      for(int j=0; j<n; j++)
        c[i][j]=inf;
    for(int i=1; i<=m; i++){
      cin>>x>>y;
      A[y].push_back(x);
      cin>>cost[x][y];
    }
    c[1][0]=0;
    for(int i=1; i<rez; i++)
      for(int j=0; j<n; j++)
        if(i&(1<<j))
          for(int k=0; k<A[j].size(); k++)
            if(i&(1<<A[j][k]))
              c[i][j]=min(c[i][j],cost[ A[j][k] ] [j] +c[i^(1<<j)][ A[j][k] ]);
    rez=inf;
    for(int i=0; i<A[0].size(); i++)
      rez=min(rez,c[(1<<n)-1][ A[0][i] ]+cost[A[0][i]][0]);
    if(rez==inf)
      cout<<"Nu exista solutie";
    else cout<< rez;
    return 0;
}