#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int cost[20][20];
vector <int> lista[20];
int c[20][500000];
int main()
{
    int n, m, i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cost[i][j] = 2e9;
    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 < n; i++)
        for (j = 0; j < (1 << n); j++)
            c[i][j] = 2e9;
    c[0][1] = 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++)
                {
                    int v = lista[j][h];
                    if (i & (1 << v))
                        c[j][i] = min(c[j][i], c[v][i ^ (1 << j)] + cost[v][j]);
                }
    int sol = 2e9, p = (1 << n);
    p--;
    for (i = 0; i < lista[0].size(); i++)
    {
        int v = lista[0][i];
        if (c[v][p] != 2e9)
            sol = min(sol, c[v][p] + cost[v][0]);
    }
    if (sol == 2e9)
        cout << "Nu exista solutie";
    else
        cout << sol;
    return 0;
}