#include <iostream>
#include <cstdio>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

int c[20][20];
vector<int> g[20];
int a[18][1<<18+1];
int n,m,x,y,ct;

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d %d", &n,&m);
    for(int i=0;i<m;++i){
        scanf("\n%d %d %d", &x,&y,&ct);
        c[x][y]=ct;
        g[y].push_back(x);
    }

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

    for(int i=1;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(int k:g[j])
                    if(i&(1<<k))
                        a[j][i]=min(a[j][i],a[k][i^(1<<j)]+c[k][j]);

    int rez=INF;
    for(int i=0;i<n;++i){
        if(c[i][0] && a[i][(1<<n)-1]!=INF)
            rez=min(rez, a[i][(1<<n)-1]+c[i][0]);
    }

    if(rez!=INF)
        cout<<rez;
    else
        cout<<"Nu exista solutie";

    return 0;
}