#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int n,m;
int cost[25][25];
int dp[(1<<18)-1][25];
int sol=1e9;
vector<int> vec[25];

int calc(int f,int e){

    if(dp[f][e]>=0)

        return dp[f][e];

    dp[f][e]=1e9;

    for(int i=0;i<vec[e].size();i++)
        if(f&(1<<vec[e][i])){

            if(vec[e][i]==0 && f!=(1<<e)+1) continue;

            dp[f][e]=min(dp[f][e],calc(f^(1<<e),vec[e][i])+cost[vec[e][i]][e]);

        }

    return dp[f][e];


}

int main(){

    cin>>n>>m;
    for(int i=0;i<m;i++){

        int x,y;
        cin>>x>>y;
        cin>>cost[x][y];
        vec[y].push_back(x);

    }

    memset(dp,-1,sizeof(dp));

    dp[1][0]=0;

    for(int i=0;i<vec[0].size();i++)
        sol=min(sol,calc((1<<n)-1,vec[0][i])+cost[vec[0][i]][0]);

    if(sol==1e9) cout<<"Nu exista solutie";
    else cout<<sol;

}