#include <bits/stdc++.h>
#define NMAX 18
#define infinity 1000000000
using namespace std;

ifstream fin{"hamilton.in"};
ofstream fout{"hamilton.out"};

int N, M, startNode = 0;

vector<vector<int>> dp(NMAX, vector<int>(1 << NMAX, infinity));
vector<vector<int>> cost(NMAX, vector<int>(NMAX, infinity));
vector<vector<int>> subset(NMAX + 1, vector<int>());

int onBitsCount(int number)
{
    int answer = 0;

    while(number)
    {
        if(number & 1) ++answer;
        number >>= 1;
    }

    return answer;
}


inline bool isBitOn(int position, int number)
{
    return (1 << position) & number;
}


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

    for(int i = 0; i < (1 << N); ++i)
        subset[onBitsCount(i)].push_back(i);


    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 == startNode) continue;
        dp[i][1 << startNode | 1 << i] = cost[startNode][i];
    }

    for(int lungime_drum = 3; lungime_drum <= N; ++lungime_drum)
    {
        for(auto& state : subset[lungime_drum])
        {
            if(isBitOn(startNode, state) == false) continue;

            for(int next = 0; next < N; ++next)
            {
                if(next == startNode || isBitOn(next, state) == false) continue;

                int previous_state = state ^ (1 << next);
                int minDist = infinity;

                for(int node = 0; node < N; ++node)
                {
                    if(node == startNode || node == next || isBitOn(node, state) == false) continue;

                    minDist = min(minDist, cost[node][next] + dp[node][previous_state]);
                }

                dp[next][state] = minDist;
            }
        }
    }

    int END_STATE = (1 << N) - 1;
    int minTour = infinity;


    for(int node = 0; node < N; ++node)
    {
        if(node == startNode) continue;

        minTour = min(minTour, dp[node][END_STATE] + cost[node][startNode]);
    }

    if(minTour == infinity)
        fout << "Nu exista solutie";
    else
        fout << minTour;
}