#include <bits/stdc++.h>
#define nmax (1<<18) + 5
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");

int n,m,a,b,c;

int cost[20][20];

vector<vector<int>> dp(nmax,vector<int>(18,2e9));

int main()
{
    fin >> n >> m;

    for(int i = 1 ; i <= m ; ++i)
    {
        fin >> a >> b >> c;

        cost[a][b]=c;
    }

    dp[1][0] = 0;

    for(int mask = 1 ; mask < (1<<n) ; mask++){
        for(int node = 0 ; node < n ; ++node){
            if((1 << node) & mask) {
                for(int k = 1 ; k < n ; ++k){
                    if(!cost[node][k] || (mask & (1 << k)))continue;

                    int next = mask ^ (1<<k);
                    dp[next][k] = min(dp[next][k],dp[mask][node] + cost[node][k]);
                }
            }
        }
    }

    int ans = 2e9+5;

    for(int i = 0 ; i < n ; ++i)
    {
        if(!cost[i][0])continue;

        ans = min(ans,dp[(1<<n)-1][i] + cost[i][0]);
    }

    if(ans == 2e9+5)
        fout << "Nu exista solutie";
    else
        fout << ans;

    return 0;
}