#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_NODES = 20;  
const int MAX_CONFIG = 262150;
const int INF = 1000000000;  

int nodeCount, edgeCount, minCycleCost;
vector<int> incomingEdges[MAX_NODES]; 
int memo[MAX_CONFIG][MAX_NODES]; 
int edgeCost[MAX_NODES][MAX_NODES]; 

int calculateMinCycleCost(int config, int lastNode) {
     if (memo[config][lastNode] == -1) {
        memo[config][lastNode] = INF;

        for (size_t i = 0; i < incomingEdges[lastNode].size(); ++i) {
            int prevNode = incomingEdges[lastNode][i];

            if (config & (1 << prevNode)) {
                if (prevNode == 0 && config != (1 << lastNode) + 1) continue;

                memo[config][lastNode] = min(
                    memo[config][lastNode],
                    calculateMinCycleCost(config ^ (1 << lastNode), prevNode) + edgeCost[prevNode][lastNode]
                );
            }
        }
    }
    return memo[config][lastNode];
}

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

    minCycleCost = INF;

    fin >> nodeCount >> edgeCount;

    for (int i = 0; i < nodeCount; ++i) {
        for (int j = 0; j < nodeCount; ++j) {
            edgeCost[i][j] = INF;
        }
    }

    for (int i = 1; i <= edgeCount; ++i) {
        int startNode, endNode, cost;
        fin >> startNode >> endNode >> cost;

        incomingEdges[endNode].push_back(startNode);
        edgeCost[startNode][endNode] = cost;
    }

    memset(memo, -1, sizeof(memo));
    memo[1][0] = 0; 

    for (size_t i = 0; i < incomingEdges[0].size(); ++i) {
        int prevNode = incomingEdges[0][i];
        minCycleCost = min(minCycleCost, calculateMinCycleCost((1 << nodeCount) - 1, prevNode) + edgeCost[prevNode][0]);
    }

    // Output the result
    if (minCycleCost == INF) {
        fout << "Nu exista solutie" << endl; 
    } else {
        fout << minCycleCost << endl; 
    }

    return 0;
}