#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

template <typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll NMAX=18,INF=1e9;
char buff[2048];
int bpos=2048;
FILE* fin;
int read(){
    int n=0;
    if(bpos==2048) bpos=0,fread(buff,1,2048,fin);
    while(buff[bpos]<'0' || buff[bpos]>'9'){
        ++bpos;
        if(bpos==2048) bpos=0,fread(buff,1,2048,fin);
    }
    while(buff[bpos]>='0' && buff[bpos]<='9'){
        n=(n<<1)+(n<<3)+(buff[bpos]^48);
        ++bpos;
        if(bpos==2048) bpos=0,fread(buff,1,2048,fin);
    }
    return n;
}
ofstream fout("hamilton.out");
int n,m,dp[1<<NMAX][NMAX],cost[NMAX][NMAX];
int outgoing[NMAX][NMAX],cntoutgoing[NMAX];
int main()
{
    fin=fopen("hamilton.in","r");
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    n=read(),m=read();
    for(int i=0;i<m;++i){
        int u=read(),v=read(),c=read();
        outgoing[u][cntoutgoing[u]++]=v;
        cost[u][v]=c;
    }
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            dp[i][j]=INF;
    dp[1][0]=0;
    for(int i=0;i<(1<<n);++i){
        for(int last=0;last<n;++last){
            if(i>>last&1)
            for(int nxt=0;nxt<cntoutgoing[last];nxt++){
                int v=outgoing[last][nxt];
                if(!(i>>v&1) && dp[i][last]+cost[last][v]<dp[i|(1<<v)][v]){
                    dp[i|(1<<v)][v]=dp[i][last]+cost[last][v];
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;++i)
        if(cost[i][0])
            ans=min(ans,dp[(1<<n)-1][i]+cost[i][0]);
    if(ans==INF)
        fout<<"Nu exista solutie";
    else fout<<ans;
    return 0;
}