#include <bits/stdc++.h>

using namespace std;

const int N=18;

vector<pair<int, int>> adj[N];

int dp[N][1<<N];

int cost[N][N];

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    memset(dp, (1<<6)-1, sizeof(dp));
    memset(cost, (1<<6)-1, sizeof(cost));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for (int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[v].push_back({u, w});
        cost[u][v]=min(cost[u][v], w);
    }
    dp[0][1]=0;
    for (int mask=1;mask<(1<<n);mask++){
        if (!(mask&1))continue;
        for (int i=0;i<n;i++){
            if ((1<<i)&mask){
                int submask=mask^(1<<i);
                for (auto [x, w]:adj[i]){
                    dp[i][mask]=min(dp[i][mask], dp[x][submask]+w);
                }
            }
        }
    }
    int ans=1e9;
    for (int i=0;i<n;i++){
        ans=min(ans, dp[i][(1<<n)-1]+cost[i][0]);
    }
    if (ans==1e9){
        cout<<"Nu exista solutie";
    }
    else{
        cout<<ans;
    }
    return 0;
}