// https://www.infoarena.ro/problema/hamilton
#include<iostream>
#include<vector>

using namespace std;

#define MOD 1000000007
#define NMAX 21
#define INF 0xfffffff

int n,m;
vector<vector<int>>dp;
vector<vector<pair<int,int>>>g;
signed main(){
    #ifdef LOCAL
        freopen("date.in","r",stdin);
    #else
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        freopen("hamilton.in","r",stdin);
        freopen("hamilton.out","w",stdout);
    #endif
    cin>>n>>m;
    
    // init
    dp.assign(1<<n,vector<int>(n,INF));
    g.resize(n);
    
    for(int i=0;i<m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    
    dp[1][0]=0;
    for(int mask=0;mask<(1<<n);++mask){
        for(int i=0;i<n;++i){
            if(!(mask&(1<<i))||dp[mask][i]==INF)continue; // i nu e in masca sau nu s-a ajuns inca la i prin configuratia curenta de noduri
            for(const auto&e:g[i]){ // vecini lui i
                int j=e.first,z=e.second;
                if(!(mask&(1<<j))){ // j nu e in masca
                    dp[mask|(1<<j)][j]=dp[mask][i]+z;
                }
            }
        }
    }
    
    // complete the cycle 
    int ans=INF;
    for(int i=0;i<n;++i){
        if(dp[(1<<n)-1][i]!=INF){
            for(const auto&e:g[i]){
                if(!e.first){ // node 0
                    ans=min(ans,dp[(1<<n)-1][i]+e.second);
                }
            }
        }
    }
    if(ans-INF)cout<<ans; // ciclul nu s-a putut completa
    else cout<<"Nu exista solutie";
    return 0;
}