#include <fstream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<pair<int, int> > L[18];
int n,m,i,x,y,c,cost,sol,smax,s,j,vecin,snext,d[18][1<<18],v[18];
int main () {
    for (i=0;i<18;i++) {
        for (j=0;j<(1<<18);j++)
            d[i][j]=INT_MAX;
        v[i]=INT_MAX;
    }
    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=INT_MAX, d[0][1]=0, smax=(1<<n);
    for (s=1;s<smax;s+=2) {
        for (i=0;i<n;i++) {
            if (d[i][s]!=INT_MAX) {
                for (j=0;j<L[i].size();j++) {
                    vecin=L[i][j].first;
                    cost=L[i][j].second;
                    if (!(s&(1<<vecin))) {
                        snext=s+(1<<vecin);
                        d[vecin][snext]=min(d[vecin][snext],d[i][s]+cost);
                    }
                }
            }
        }
    }
    for (i=1;i<n;i++) {
        if (v[i]!=INT_MAX&&d[i][smax-1]!=INT_MAX)
            sol=min(sol,d[i][smax-1]+v[i]);
    }
    if (sol!=INT_MAX)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    return 0;
}