#include <fstream>
#include <vector>

using namespace std;

vector <int> g[19];
int cost [20][20];
int c[262150][20];

int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

int main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");

    int n, m;
    in >> n >> m;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cost[i][j] = 10000000;

    for (int i = 0; i < 1<<n; ++i)
        for (int j = 0; j < n; ++j)
            c[i][j] = 10000000;

    int x, y;
    for (int i = 1; i <= m; ++i)
    {
        in >> x >> y;
        g[y].push_back(x);
        in >> cost[x][y];
    }
    c[1][0] = 0;
    for (int i = 0; i < 1<<n; ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1<<j))
                for (size_t k = 0; k < g[j].size(); ++k)
                    if (i & (1<<g[j][k]))
                        c[i][j] = min(c[i][j], c[i ^ (1<<j)][g[j][k]] + cost[g[j][k]][j]);

    int sol = 10000000;
    for (size_t i = 0; i < g[0].size(); i++)
        sol = min(sol, c[(1<<n)-1][g[0][i]] + cost[g[0][i]][0]);

    if (sol == 10000000)
        out << "Nu exista solutie\n";
    else
        out << sol << '\n';

    return 0;
}