#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define cin fin
#define cout fout

#define N 19
#define inf 1000000000
int n, m, x, y, c, cost[N][N], dp[1<<N][N];
vector < vector < int > > gr;

int main()
{
    cin >> n >> m;
    gr.resize(n+5);
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            cost[i][j] = inf;
        }
    }
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> c;
        cost[x][y] = c;
        gr[y].push_back(x);
    }
    for(int i = 0 ; i < (1<<n) ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            dp[i][j] = inf;
        }
    }
    dp[1][0] = 0;
    for(int config = 0 ; config < (1<<n) ; config++)
    {
        for(int nod = 0 ; nod < n ; nod++)
        {
            if((1<<nod)&config)
            {
                for(auto t : gr[nod])
                {
                    if((1<<t)&config)
                    {
                        dp[config][nod] = min(dp[config][nod],dp[config^(1<<nod)][t]+cost[t][nod]);
                    }
                }
            }
        }
    }
    int rez = inf;
    for(auto t : gr[0])
    {
        rez = min(rez,dp[(1<<n)-1][t]+cost[t][0]);
    }
    if(rez == inf)cout << "Nu exista solutie";
    else cout << rez;
	return 0;
}