#include <stdio.h>
#include <cstring>
#include <vector>
#define nmax 19
#define pmax 270000
#define inf 0x3f3f3f3f
using namespace std;
int n,m,i,j,k,x,y,cost[nmax][nmax],maxx,dp[pmax][nmax];
vector <int> g[nmax];
int main() {
freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
scanf("%d %d",&n,&m); maxx=1<<n;
memset(cost,inf,sizeof(cost));
memset(dp,inf,sizeof(dp));
for (i=1;i<=m;i++) {
    scanf("%d %d",&x,&y);
    g[y].push_back(x);
    scanf("%d",&cost[x][y]);
}
dp[1][0]=0;
for (i=0;i<maxx;i++) {
    for (j=0;j<n;j++)
       if ((i>>j)&1==1) {
           for (k=0;k<g[j].size();k++)
              if ((i>>g[j][k])&1==1) {
                  dp[i][j]=min(dp[i][j],dp[i^(1<<j)][g[j][k]]+cost[g[j][k]][j]);
              }
       }
}
int sol=inf;
for (i=0;i<g[0].size();i++)
    sol=min(sol,dp[maxx-1][g[0][i]]+cost[g[0][i]][0]);
if (sol==inf) puts("Nu exista solutie"); else
printf("%d",sol);
return 0;
}