#include <cstdio>
#include <vector>

using namespace std;

const int inf=1e9;
vector<int> g[20];
int d[1<<18][20],cost[20][20];

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int n,m,x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        cost[x][y]=c;
        g[x].push_back(y);
    }
    int lim=1<<n;
    for(int mask=0;mask<lim;mask++)
        for(int i=0;i<n;i++) d[mask][i]=inf;
    d[1][0]=0;
    for(int mask=1;mask<lim;mask++)
        for(int i=0;i<n;i++)
            if(mask&(1<<i))
                for(vector<int>::iterator it=g[i].begin();it!=g[i].end();it++)
                    if((mask&(1<<*it))==0)
                        d[mask|(1<<*it)][*it]=min(d[mask|(1<<*it)][*it],d[mask][i]+cost[i][*it]);
    int sol=inf;
    for(int i=0;i<n;i++)
        if(cost[i][0]) sol=min(sol,d[lim-1][i]+cost[i][0]);
    if(sol==inf) printf("Nu exista solutie!");
    else printf("%d",sol);
    return 0;
}