#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,i,j,x,y,c,stare,sol,staremax,urmstare,vecin,cost,v[18],d[18][1<<18];
vector< pair<int,int> > L[18];
int main() {
    for (i=0;i<18;i++) {
        for (j=0;j<(1<<18);j++)
            d[i][j]=inf;
        v[i]=inf;
    }
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back({y,c});
        if (y==0)
            v[x]=c;
    }
    sol=inf;
    d[0][1]=0, staremax=(1<<n)-1;
    for (stare=1;stare<=staremax;stare+=2) {
        for (i=0;i<n;i++) {
            if (d[i][stare]!=inf) {
                for (auto it:L[i]) {
                    vecin=it.first;
                    cost=it.second;
                    if (!(stare&(1<<vecin))) {
                        urmstare=stare|(1<<vecin);
                        d[vecin][urmstare]=min(d[vecin][urmstare],d[i][stare]+cost);
                    }
                }
            }
        }
    }
    for (i=1;i<n;i++)
        if (v[i]!=inf&&d[i][staremax]!=inf)
            sol=min(sol,d[i][staremax]+v[i]);
    if (sol!=inf)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    return 0;
}