#include<fstream>
#include<vector>

using namespace std;

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

int DP[263000][18];
int N,M,R,Sol=2000000000;
vector <pair<int,int>> G[18];

int main(){
    fin>>N>>M;
    R=1<<N;
    for(int i=1;i<=M;i++){
        int X,Y,Z;
        fin>>X>>Y>>Z;
        G[Y].push_back(make_pair(X,Z));
    }
    for(int i=0;i<263000;i++)
        for(int j=0;j<18;j++)
            DP[i][j]=2000000000;
    DP[1][0]=0;
    for(int i=3;i<R;i++)
        for(int j=0;j<N;j++)
           if(i&(i<<j)){
             int B=i^(1<<j);
             for(int k=0;k<G[j].size();k++)
                 if(B&(1<<G[j][k].first))
                   DP[i][j]=min(DP[i][j],DP[B][G[j][k].first]+G[j][k].second);
    }
    for(int i=0;i<G[0].size();i++){
        Sol=min(Sol,DP[R-1][G[0][i].first]+G[0][i].second);
    }
    if(Sol==2000000000)
        fout<<"Nu exista solutie"<<'\n';
    else
        fout<<Sol<<'\n';
}