#include <fstream>
#include <iostream>
#define V 18

using namespace std;

const int N = 1<<18;

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

int dp[N][V];
const int INF = 1e9;
int c[V][V];

int main()
{
    int n,m;
    in >> n >> m;
    for(int i = 0 ; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            c[i][j] = INF * (i!=j);
        }
        for(int j = 0; j<(1<<n); j++)
        {
            dp[j][i] = INF;
        }
    }
    for(int i=0; i<m; i++)
    {
        int x,y,e;
        in >> x >> y >> e;
        c[x][y]=e;
    }
    dp[1][0]=0;
    for(int i=1; i<(1<<n); i+=2)
    {
        for(int j=0; j<n; j++)
        {
            if(i&(1<<j))
            {
                for(int k=0; k<n; k++)
                {
                    if(!(i&(1<<k))&& c[j][k]!=INF)
                    {
                        int u = (i | (1<<k));
                        dp[u][k] = min(dp[u][k], dp[i][j] + c[j][k]);
                    }
                }
            }
        }
    }
    int ans=INF;
    for(int i=1; i<n; i++)
    {
        if(c[i][0] != INF)
        {
            ans = min(ans,dp[(1<<n)-1][i] + c[i][0]);
        }
    }
    if(ans == INF)
        out<<"Nu exista solutie";
    else
        out<<ans;
    return 0;
}