#include<fstream>
#include<list>
using namespace std;

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

const int NMAX = 19, INF = 15e8;

list<int> adjList[NMAX];

int minCostCyc[(1 << NMAX) + 5][NMAX], costMatrix[NMAX][NMAX];
int nodesCnt, edgesCnt;

inline void readData(){

    fin >> nodesCnt >> edgesCnt;

    int from, to, cost;
    while(edgesCnt--){

        fin >> from >> to >> cost;
        adjList[to].push_back(from);
        costMatrix[from][to] = cost;
    }
}

inline void initialize(){

    int mask, node;
    for(mask = 0; mask < (1 << nodesCnt); ++mask)
        for(node = 0; node < nodesCnt; ++node)
            minCostCyc[mask][node] = INF;
    minCostCyc[1][0] = 0;
}

inline void GoDP(){

    int mask, node;
    for(mask = 1; mask < (1 << nodesCnt); ++mask)
        for(node = 0; node < nodesCnt; ++node)
            if(mask & (1 << node))
                for(const int &nextNode : adjList[node])
                    if(mask & (1 << nextNode))
                        minCostCyc[mask][node] = min(minCostCyc[mask][node], minCostCyc[mask ^ (1 << node)][nextNode] + costMatrix[nextNode][node]);

    int bestCyc = INF;

    for(const int &nextNode : adjList[0])
        bestCyc = min(bestCyc, minCostCyc[(1 << nodesCnt) - 1][nextNode] + costMatrix[nextNode][0]);

    if(bestCyc == INF)
        fout << "Nu exista solutie";
    else
        fout << bestCyc;
}

int main(){

    readData();
    initialize();
    GoDP();
}