#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][300010];
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);
}



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

    }
}

int cst=10e17;
for(int j=0; j<n; j++){
        for(int i=0; i<1; i++){
    if( (c[j][i]>0) && ( g[j][(((int)1)<<n)-1-(((int)1)<<(j) ) ]>0 || (n==2) ) && (i!=j) ){
        cst=min(cst, c[j][i]+g[j][(((int)1)<<n)-1-(((int)1)<<(j) ) ]);
    }
        }
}
if(cst>=(10e17)){
    cout<<"Nu exista solutie";
}
else{
    cout<<cst;
}


return 0;
}