#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[20][260010];
vector<int> msk[20];
vector<int> bts[260010];

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++){
    if( (i&(1LL) )>0){continue;}
    msk[count_bits(i)].pb(i);
    for(int j=1; (((int)1)<<j)<=i; j++){
        if( (i&(((int)1)<<j))>0){
            bts[i].pb(j);
        }
    }
}

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:bts[b]){
                if( (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]);
                }
                //cout<<c[j][i]<<" ";
            }
            //cout<<"||"<<cm<<" "<<i<<" "<<b<<"\n";
        if(cm>=10e17){
            g[i][b]=0;
        }
        else{
            g[i][b]=cm;
        }
        }

    }
}


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



return 0;
}