#include <bits/stdc++.h>

#define VMAX 1000000
#define NMAX 18
#define LOG 20

#define INF (long long)(1e9)
#define MOD 666013
#define BASE 23

#define BLOCK_SIZE 230
#define ll long long int
#define EPS 0.02

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


vector<pair<int,int>> adj[NMAX+1],adjT[NMAX+1];
int dp[1<<NMAX][NMAX];

int n,m;
int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
        adjT[y].push_back({x,c});
    }
    for(int mask=0;mask < (1<<n);++mask)
    {
        for(int i=0;i<n;i++)
        {
            dp[mask][i] = INF;
        }
    }
    dp[1][0]=0;
    for(int mask=1;mask <(1<<n);mask++)
    {
        if(!(mask & 1))continue;
        for(int i=1;i<n;i++)
        {
            if(!(mask & (1<<i)))continue;
            for(auto e : adjT[i])
            {
                int j = e.first;
                int c = e.second;
                if(mask & (1<<j))
                {
                    dp[mask][i] = min(dp[mask][i],dp[mask^(1<<i)][j] + c);
                }
            }
        }
    }
    int mn=INF;
    for(int i=1;i<n;i++)
    {
        for(auto [j,c] : adj[i])
        {
            if(j==0)
            {
                mn=min(mn,dp[(1<<n)-1][i]+c);
            }
        }
    }
    if(mn==INF)
    {
        fout << "Nu exista solutie";
    }
    else
    {
        fout << mn;
    }




}