#include <fstream>
#include <iostream>
#include <vector>
#include <limits>
#include <bitset>
#include <cstdlib>
#include <cstdio>

#define MAXN 18
#define BIT(index) (1<<(index))
#define FULL_PATH_MASK(n) ((~(0xffffffff << (n))))

using namespace std;

typedef unsigned int uint32;

struct Edge
{
    Edge() :
        vertexID(0),
        cost(0)
    {}

    Edge(uint32 vID, int c) :
        vertexID(vID),
        cost(c)
    {}

    uint32 vertexID;
    int cost;
};

typedef vector<vector<Edge> > Graph;

Graph graph;

int costMatrix[1<<MAXN][MAXN];

int main()
{
    uint32 n, m;
    fstream fin("hamilton.in", fstream::in);
    fstream fout("hamilton.out", fstream::out);
    
    fin >> n >> m;
    //cout << n << endl;
    
    graph.resize(n);
    
    for (int i=0; i<m; ++i)
    {
        uint32 x, y;
        int cost;

        fin >> x >> y >> cost;
        graph[y].push_back(Edge(x, cost));
    }

    /*for (auto& var : graph)
    {
        static int i = 0;
        cout << i++ << " <-- ";
        
        for (auto& edge : var)
        {
            cout << "(" << (int)edge.vertexID << " " << edge.cost << ") "; 
        }
        cout << endl;
    }*/
    
    for (uint32 possiblePath=0; possiblePath<(1<<n); ++possiblePath)
    {
        for (uint32 dest=1; dest<n; ++dest)
        {
            costMatrix[possiblePath][dest] = numeric_limits<int>::max()/2;
        }
    }
    
    for (uint32 possiblePath=1; possiblePath<(1<<n); ++possiblePath)
    {
        if ((possiblePath & 1) == 0) continue;

        for (uint32 dest=1; dest<n; ++dest)
        {
            if ((possiblePath & BIT(dest)) == 0) continue;

            for (int source=0; source<graph[dest].size(); ++source)
            {
                if ((possiblePath & BIT(graph[dest][source].vertexID)) == 0) continue;
                
                if ((possiblePath xor BIT(dest)) > 1 && graph[dest][source].vertexID == 0) continue;
                
                costMatrix[possiblePath][dest] =
                    min(costMatrix[possiblePath][dest],
                        graph[dest][source].cost + costMatrix[possiblePath xor BIT(dest)][graph[dest][source].vertexID]);
                
                /*cout << dest << " " << graph[dest][source].vertexID << " "
                     << std::bitset<19>(possiblePath) << " "
                     << possiblePath << " "
                     << costMatrix[possiblePath][dest] << endl;
                getchar();*/
                //cout << graph[dest][source].cost + costMatrix[possiblePath xor BIT(dest)][graph[dest][source].vertexID] << endl;
            }
        }
    }
    
    /*for (uint32 i=0; i<n; ++i)
    {
        cout << costMatrix[FULL_PATH_MASK(n)][i] << " ";
    }
    cout << endl;*/
    
    int minCost = numeric_limits<int>::max()/2;
    for (int i=0; i<graph[0].size(); ++i)
    {
        minCost = min(minCost, graph[0][i].cost + costMatrix[FULL_PATH_MASK(n)][graph[0][i].vertexID]);
    }
    
    if (minCost < numeric_limits<int>::max()/2)
    {
        fout << minCost << endl;
    }
    else
    {
        fout << "Nu exista solutie\n";
    }

    return 0;
}