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

using namespace std;

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

const int NMAX = 18 + 5;
const int MMAX = (1 << 18) + 5;
const int INF = 0x3f3f3f3f;

vector <int> graph[NMAX];
int n, m, minim;
int cost[NMAX][NMAX], dp[MMAX][NMAX];

void init_cost()
{
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cost[i][j] = INF;
}

void init_dp()
{
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            dp[i][j] = INF;
    dp[1][0] = 0;
    minim = INF;
}

void read()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> c;
        graph[y].push_back(x);
        cost[x][y] = c;
    }
}

int main()
{
    init_cost();
    read();
    init_dp();

    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                for (int k = 0; k < graph[j].size(); ++k)
                    if (i & (1 << graph[j][k]))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][graph[j][k]] + cost[graph[j][k]][j]);

    for (int i = 0; i < graph[0].size(); ++i)
        minim = min(minim, dp[(1 << n) - 1][graph[0][i]]+cost[graph[0][i]][0]);

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

    return 0;
}