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

#define MAXN 19
#define MAX_SIZE (1<<MAXN)
#define BIT(n) (1<<(n))
#define FULL_PATH(n) (~(0xffffffff << (n)))

using namespace std;

typedef unsigned int uint32;

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

typedef vector<vector<Edge> > Graph;

Graph graph;

uint32 matrix[MAX_SIZE][MAXN];

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

        fin >> x >> y >> c;
        graph[x].push_back(Edge(y,c));
        
        if (y == 0)
        {
            vToSource.push_back(Edge(x,c));
        }
    }
    
    /*for (auto& var : graph)
    {
        static int i=0;
        
        cout << i++ << " -> ";
        for (Edge& edge : var)
        {
            cout << "(" << edge.vertexID << ", " << edge.cost << ")  ";
        }
        cout << "\n";
    }
    
    cout << "\n";
    
    for (Edge& edge : vToSource)
    {
        cout << "(" << edge.vertexID << ", " << edge.cost << ")  ";
    }
    cout << "\n";*/
    
    for (int i=0; i<(1<<n); ++i)
    {
        for (int j=0; j<n; ++j)
        {
            matrix[i][j] = numeric_limits<uint32>::max()/2;
        }
    }
    
    matrix[1][0] = 0;
    
    for (uint32 path=0; path<(1<<n); ++path)
    {
        if ((path & 1) == 0) continue;

        for (short src=0; src<n; ++src)
        {
            if ((BIT(src) & path) == 0) continue;
            if ((src == 0) && __builtin_popcount((path-1))>1) continue;

            for(short dest=0; dest<graph[src].size(); ++dest)
            {
                if ((BIT(graph[src][dest].vertexID) & path) == 0) continue;
                
                matrix[path][graph[src][dest].vertexID] =
                    min(matrix[path][graph[src][dest].vertexID],
                        graph[src][dest].cost + matrix[path xor BIT(graph[src][dest].vertexID)][src]);
            }
        }
    }

    uint32 minDist = numeric_limits<uint32>::max()/2;
    for (int i=0; i<vToSource.size(); ++i)
    {
        if (matrix[FULL_PATH(n)][vToSource[i].vertexID] + vToSource[i].cost < minDist)
        {
            minDist = matrix[FULL_PATH(n)][vToSource[i].vertexID] + vToSource[i].cost;
        }
    }
    
    if (minDist >= numeric_limits<uint32>::max()/2)
    {
        fout << "Nu exista solutie\n";
    }
    else
    {
        fout << minDist << endl;
    }

    return 0;
}