#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
vector<vector<int>>dp;
vector<int>muchie_0;
vector<vector<pair<int,int>>>gr;
const int inf=1e9;

int main(){
    
    int n,nr_sub,nod1,nod2,val,m,cost;
    cin>>n>>m;
    nr_sub=(1<<n)-1;
    gr.resize(n);
    muchie_0.resize(n,0);

    for(int i=0;i<=m-1;i++){
        cin>>nod1>>nod2>>cost;
        gr[nod1].push_back({nod2,cost});

        if(nod2==0){
            muchie_0[nod1]=cost;
        }

    }

    dp.resize(nr_sub+1,vector<int>(n,inf));
    dp[1][0]=0;
   
    for(int i=1;i<=nr_sub;i++){
        for(int nod=0;nod<=n-1;nod++){
            for(const auto&vecin:gr[nod]){
                if(i&(1<<nod) && dp[i^(1<<vecin.first)][nod]+vecin.second<dp[i|(1 << vecin.first)][vecin.first]){
                  dp[i|(1 << vecin.first)][vecin.first]=dp[i^(1<<vecin.first)][nod]+vecin.second;
                }
            }
        }
    }
  
    val=inf;

    for(int i=1;i<=n-1;i++){
        if(muchie_0[i]!=0){
            val=min(val,dp[nr_sub][i]+muchie_0[i]);
        }
         
    }
    if(val==inf){
        cout<<"Nu exista solutie";
    }else{
         cout<<val;
    }
}