#include <fstream>
#include <vector>
#include <climits>
#define X first
#define Y second
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,i,x,y,c,v[20],D[20][(1<<18)],sol,j,stmax,k;
vector<pair<int,int> > L[20];
int main(){
    fin>>n>>m;
    for(i=0;i<n;i++)
        v[i]=INT_MAX;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
        if(y==0)
            v[x]=c;
    }
    for(i=0;i<20;i++)
        for(j=0;j<(1<<18);j++)
            D[i][j]=INT_MAX;
    stmax=(1<<n);
    D[0][1]=0;
    for(i=1;i<stmax;i+=2)
        for(j=0;j<n;j++)
            if(D[j][i]!=INT_MAX){
                for(k=0;k<L[j].size();k++){
                    int vec=L[j][k].X;
                    int cost=L[j][k].Y;
                    if(!(i&(1<<vec)))
                        D[vec][i+(1<<vec)]=min(D[vec][i+(1<<vec)],D[j][i]+cost);

                }
            }

    sol=INT_MAX;
    for(i=1;i<n;i++)
        if(D[i][(1<<n)-1]!=INT_MAX&&v[i]!=INT_MAX)
            sol=min(sol,D[i][(1<<n)-1]+v[i]);
    if(sol!=INT_MAX)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    return 0;
}