#include <bits/stdc++.h>
#define dim 18
#define inf 0x3f3f3f3f
#define x first
#define y second
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector <pair<int,int> > v[dim];
int d[dim][1<<dim],cost[dim];
int n,m,sol,a,b,c,i,j,stare,Last,Cost,Next,vecin;
int main(){
    memset(d,inf,sizeof(d));
    memset(cost,inf,sizeof(cost));
    sol=inf;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        if(b==0){
            cost[a]=c;
        }
    }
    d[0][1]=0;
    for(stare=1 ; stare < (1<<n) ; stare+=2){
        for(i=0;i<n;i++){
            if(d[i][stare]!=inf){
                for(j=0 ; j<v[i].size();j++){
                    vecin = v[i][j].x;
                    Cost = v[i][j].y;
                    if((stare & 1<<vecin) == 0){
                        Next = stare + (1<<vecin);
                        d[vecin][Next]=min(d[vecin][Next],d[i][stare]+Cost);
                    }
                }
            }
        }
    }
    Last = 1<<n;
    Last--;
    for(i=1 ; i<n ; i++){
        if(cost[i]!=inf && d[i][Last]!=inf ){
           sol=min(sol,d[i][Last]+cost[i]);
        }
    }
    if(sol!=inf){
        fout<<sol<<"\n";
    }
    else{
        fout<<"Nu exista solutie";
    }




    return 0;
}