#include <bits/stdc++.h>

using namespace std;

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

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

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, start_node = 0;

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 = 0; i < N; ++i)
    {
        if(i == start_node) continue;

        DP[i][(1 << i) | (1 << start_node)] = COST[start_node][i];
    }

    for(int next_state = 0; next_state < (1 << N); ++next_state)
    {
        if(((1 << start_node) & next_state) == false) continue;

        for(int next_node = 0; next_node < N; ++next_node)
        {
            if(((1 << next_node) & next_state) == false || next_node == start_node) continue;

            int current_state = next_state ^ (1 << next_node);

            for(int current_node = 0; current_node < N; ++current_node)
            {
                if(((1 << current_node) & current_state) == false || current_node == next_node || current_node == start_node) continue;

                DP[next_node][next_state] = min(DP[next_node][next_state], DP[current_node][current_state] + COST[current_node][next_node]);
            }
        }
    }

    int minCost = oo;
    int final_state = (1 << N) - 1;

    for(int i = 0; i < N; ++i)
    {
        if(i == start_node) continue;

        minCost = min(minCost, DP[i][final_state] + COST[i][start_node]);
    }

    if(minCost == oo)
    {
        fout << "Nu exista solutie";
    }
    else
    {
        fout << minCost;
    }
}