#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 18;
const int oo = 1 << 29;

vector<vector<int>> cost(N_MAX, vector<int>(N_MAX, oo));
vector<vector<int>> dp(N_MAX, vector<int>(1 << N_MAX, oo));

int N, M;

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;

        cost[x][y] = c;
    }

    for(int i = 1; i < N; ++i)
        dp[i][1 | 1 << i] = cost[0][i];


    for(int state = 1; state < (1 << N); ++state)
    {
        if((state & 1) == false) continue;

        for(int node = 1; node < N; ++node)
        {
            if((state & (1 << node)) == false) continue;

            int prev_state = state ^ (1 << node);

            for(int prev_node = 1; prev_node < N; ++prev_node)
            {
                if(prev_node == node || (prev_state & (1 << prev_node)) == false) continue;
                dp[node][state] = min(dp[node][state], dp[prev_node][prev_state] + cost[prev_node][node]);
            }
        }
    }

    int min_cost = oo;

    for(int i = 1; i < N; ++i)
        min_cost = min(min_cost, dp[i][(1 << N) - 1] + cost[i][0]);


    if(min_cost == oo)
        fout << "Nu exista solutie";
    else
        fout << min_cost;

}