#include <bits/stdc++.h>

using namespace std;
const int INF=1e9;
int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin>>n>>m;
    vector<vector<int>>cost(n,vector<int>(n,INF));
    vector<vector<int>>dp((1<<n), vector<int>(n,INF));
    vector<vector<int>>in(n);
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        cin>>x>>y>>c;
        cost[x][y]=c;
        in[y].push_back(x);
    }
    dp[1][0]=0;
    for(int mask=3; mask<(1<<n); mask+=2)
        for(int i=1; i<n; i++)
            if(mask&(1<<i))
                for(auto v:in[i])
                    dp[mask][i]=min(dp[mask][i], dp[mask-(1<<i)][v]+cost[v][i]);

    int ans=INF;
    for(int i=1;i<n;i++)
    {
        ans=min(ans, dp[(1<<n)-1][i]+cost[i][0]);
    }
    if(ans==INF)
        cout<<"Nu exista solutie";
    else cout<<ans;
    return 0;
}