#include <fstream>
#include <climits>
#include <vector>

using namespace std;

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

unsigned int N, M;
unsigned int x, y, c;

vector <unsigned int> G[18];
unsigned int cost[19][19];
unsigned int sol[(1<<19)][19];
unsigned int i, j, k;

unsigned int solution;

int main ()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y >> c;
        G[y].push_back(x);
        cost[x][y] = c;
    }
    for (i=0; i<(1<<N); i++)
        for (j=0; j<N; j++)
            sol[i][j] = UINT_MAX;
    sol[1][0] = 0;
    for (i=0; i<(1<<N); i++)
        for (j=0; j<N; j++)
            if (i&(1<<j))
                for (k=0; k<G[j].size(); k++)
                    sol[i][j] = min(sol[i^(1<<j)][G[j][k]]+cost[G[j][k]][j],sol[i][j]);
    solution = UINT_MAX;
    for (i=0; i<G[0].size(); i++)
        solution = min(solution,sol[(1<<N)-1][G[0][i]]+cost[G[0][i]][0]);
    if (solution != UINT_MAX)
        fout << solution;
    else
        fout << "Nu exista solutie";
    return 0;
}