#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define inf 0x3f3f3f3f
#define nmax 20
#define pmax 262150
using namespace std;
int n,x,y,z,m,i,j,k,maxx,cost[nmax][nmax],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));
for (i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
    g[y].push_back(x);
    cost[x][y]=z;
}
for (i=0;i<pmax;i++)
    for (j=0;j<nmax;j++) dp[i][j]=inf;
dp[1][0]=0;
for (i=0;i<maxx;i++)
    for (j=0;j<n;j++)
        if ((i>>j)&1) {
            for (k=0;k<g[j].size();k++)
            if ((i>>g[j][k])&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) printf("Nu exista solutie"); else
    printf("%d",sol);
return 0;
}