#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> msk[20];


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


for(int sz=2; sz<=n; sz++){
    for(int b:msk[sz-1]){
        for(int i=1; i<n; i++){
            int cm=10e17;
            for(int j=0; (1LL<<j)<=b; j++){
                if( ( (b&(1LL<<j))>0 ) && (i!=j) && (c[j][i]>0) && ( (b&(1LL<<i))==0) && ( (g[j][b^(1LL<<j)]>0) || (sz==2) ) ){
                    cm=min(cm, g[j][b^(1LL<<j)]+c[j][i]);
                }
            }
        if(cm>=10e17){
            g[i][b]=0;
        }
        else{
            g[i][b]=cm;
        }

        }

    }
}




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;
}