#include <stdio.h>
#include <vector>
#define mp make_pair
#define s1 second
#define f1 first
#define inf 0x3f3f3f3f
using namespace std;

int n,m,x,y,cost,dp[(1<<18)+5][20];
bool fr[(1<<18)+5][20];
vector < pair<int,int> > g[20];

int memo(int mask,int nod)
{
    if (mask==0) return 0;
    if (fr[mask][nod]) return dp[mask][nod];
    fr[mask][nod]=true;
    for (unsigned int i=0;i<g[nod].size();i++)
        if (((mask>>g[nod][i].f1)&1)==1)
            dp[mask][nod]=min(dp[mask][nod],memo(mask-(1<<g[nod][i].f1),g[nod][i].f1)+g[nod][i].s1);
    return dp[mask][nod];
}

int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        scanf("%d %d %d",&x,&y,&cost);
        g[y].push_back(mp(x,cost));
    }
    for (int i=0;i<(1<<n);i++)
        for (int j=0;j<n;j++)
        dp[i][j]=inf;
    int mask=(1<<n)-1; dp[1][0]=0;
    for (int i=0;i<g[0].size();i++)
        dp[mask][i]=memo(mask-(1<<g[0][i].f1),g[0][i].f1)+g[0][i].s1;
    int sol=inf;
    for (int i=0;i<n;i++) sol=min(sol,dp[(1<<n)-1][i]);
    if (sol==inf) { puts("Nu exista solutie"); return 0; }
        printf("%d",sol);
    return 0;
}