#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll


ifstream fin("hamilton.in"); ofstream fout("hamilton.out");
#define cin fin
#define cout fout

int t, n, m;
int c[20][20];
int g[19][263010];
vector<int> grf[19];


int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=m; i++){
    int u, v; cin>>u>>v; cin>>c[u][v];
    grf[u].pb(v);
}


    for(int b=1; b<(1LL<<n); b++){

            for(int j=0; (1LL<<j)<=b; j++){
                for(int i:grf[j]){

                if( ( (b&(1LL<<j))>0 )  && (c[j][i]>0) && ( (b&(1LL<<i))==0) && ( (g[j][b^(1LL<<j)]>0) || (b==1) ) ){
                    if(g[i][b]==0){
                    g[i][b]=g[j][b^(1LL<<j)]+c[j][i];}else{g[i][b]=min(g[i][b],g[j][b^(1LL<<j)]+c[j][i] ) ;}
                }

                }
            }


    }





int res=10e17, fin=(1LL<<n)-1;

for(int i=1; i<n; i++){
    if( (g[i][fin^(1LL<<i)]>0) && (c[i][0]>0) ){
        res=min(res, g[i][fin^(1LL<<i)]+c[i][0]);
    }
}
if(res>=10e17){
    cout<<"Nu exista solutie";
}
else{cout<<res;}



return 0;
}