#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<int>G[25];
int cost[25][25];
int dp[20][300005];
bool mat[20][300005];
int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int n,m,a,b,val;fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b>>val;
        G[a].push_back(b);
        cost[a][b]=val;
    }
    mat[0][(1<<0)]=1;int nod;
    for(int nr=1;nr<(1<<n);nr++){
        for(int i=0;i<n;i++){
            if((nr&(1<<i))!=0){
                for(int j=0;j<G[i].size();j++){
                    nod=G[i][j];
                    if((nr&(1<<nod))!=0&&mat[i][nr^(1<<nod)]==1){
                        mat[nod][nr]=1;
                        if(dp[nod][nr]==0){
                            dp[nod][nr]=dp[i][nr^(1<<nod)]+cost[i][nod];
                        }
                        else{
                            dp[nod][nr]=min(dp[nod][nr],dp[i][nr^(1<<nod)]+cost[i][nod]);
                        }
                    }
                }
            }
        }
    }
    int min1=INT_MAX;
    for(int i=0;i<n;i++){
        if(mat[i][(1<<n)-1]==1&&cost[i][0]!=0){
            dp[i][(1<<n)-1]+=cost[i][0];
            min1=min(min1,dp[i][(1<<n)-1]);
        }
    }
    if(min1==INT_MAX){
        fout<<"Nu exista solutie"<<'\n';
    }
    else{
        fout<<min1<<'\n';
    }
    return 0;
}