#include<fstream>
#include<vector>
#define INF 1000000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,c,p,next,vecin,s,ok;
int v[50];
int D[20][1<<18];
vector<pair<int,int> > L[20];
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
        if(y==0)
            v[x]=c;
    }
    p=1<<n;
    for(int i=0;i<n;i++)
        for(int j=0;j<p;j++)
            D[i][j]=2000000000;
    p--;
    D[0][1]=0;
    for(int i=1;i<=p;i+=2)
        for(int j=0;j<n;j++){
            if(D[j][i]!=2000000000){
                for(int k=0;k<L[j].size();k++){
                    vecin=L[j][k].first;
                    c=L[j][k].second;
                    if(!(i&(1<<vecin))){
                        next=i+(1<<vecin);
                        D[vecin][next]=min(D[vecin][next],D[j][i]+c);
                    }
                }
            }
        }
    s=2000000000;
    for(int i=1;i<n;i++)
        if(v[i]!=0 && D[i][p]!=2000000000){
            ok=1;
            s=min(s,D[i][p]+v[i]);
        }
    if(ok!=0)
        fout<<s;
    else
        fout<<"Nu exista solutie";
    return 0;
}