#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int cost[20][20];
int dp[1 << 20][20];
vector <int> lista[20];
int main()
{
    int n, m, i, j, sol = 1e9;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cost[i][j] = 1e9;
    for (i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        cin >> cost[x][y];
        lista[y].push_back(x);
    }
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            dp[i][j] = 1e9;
    dp[1][0] = 0;
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            if (i & (1 << j))
                for (int h = 0; h < lista[j].size(); h++)
                    if (i & (1 << lista[j][h]))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][lista[j][h]] + cost[lista[j][h]][j]);
    for (i = 0; i < lista[0].size(); i++)
        sol = min(sol, cost[lista[0][i]][0] + dp[(1 << n) - 1][lista[0][i]]);
    if (sol == 1e9)
        cout << "Nu exista solutie";
    else
        cout << sol;
    return 0;
}