#include <fstream>
#include <vector>
#define INF 2147483647
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");

int n,m,i,j,x,y,c,k,aux,sm,vecin,cost,sol,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(make_pair(y,c));
        if (!y)
            v[x]=c;
    }
    sm=(1<<n);
    D[0][1]=0;
    for (k=1;k<sm;k+=2)
        for (i=0;i<n;i++)
            if (D[i][k]!=INF)
                for (j=0;j<L[i].size();j++){
                    vecin=L[i][j].first;
                    cost=L[i][j].second;
                    if (!(k&(1<<vecin))){
                        aux=k+(1<<vecin);
                        D[vecin][aux]=min(D[vecin][aux],D[i][k]+cost);
                    }
                }
    sol=INF;
    for (i=1;i<n;i++)
        if (v[i]!=INF && D[i][sm-1]!=INT_MAX)
            sol=min(sol,D[i][sm-1]+v[i]);
    if (sol!=INF)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    fin.close();
    fout.close();
    return 0;
}