#include <bits/stdc++.h>
using namespace std;

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

const int NMAX= 20, INF=1e9;
int t;
int dp[1<<20][NMAX], cost[NMAX][NMAX];

int main(){
    int n, m;
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=INF;

    for(int i=1;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            dp[i][j]=INF;

    while(m--){
        int x, y, w;
        fin>>x>>y>>w;
        cost[x][y]=w;
    }
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i++){
        //cout<<endl<<"i= "<<i<<endl;
        for(int j=0;j<n;j++){
            //cout<<"j= "<<j<<' '<<(i&(1<<j))<<endl;
            if((i&(1<<j))!=0){
                for(int k=0;k<n;k++){
                    //cout<<"k= "<<k<<endl;
                    if((i&(1<<k))==0){
                        dp[(i|(1<<k))][k]=min(dp[i|(1<<k)][k], dp[i][j]+cost[j][k]);
                        //cout<<(i|(1<<k))<<' '<<k<<' '<<dp[i|(1<<k)][k]<<endl;
                    }
                }
            }
        }
    }

    int ans=INF;
    for(int j=0;j<n;j++){
        ans=min(ans, dp[(1<<n) -1][j]+cost[j][0]);
    }
    if(ans!=INF)
        fout<<ans;
    else
        fout<<"Nu exista solutie";

    return 0;
}