#include <fstream>

using namespace std;

#define N 20
#define M 310
#define INF (1 << 31 - 1)

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

int n, m;
int lst[N], vf[M], urm[M], cost[M], nr;
int d[1 << N][N];

int minim(int x, int y)
{
    return x < y ? x : y;
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;

        vf[++nr] = x;
        cost[nr] = c;
        urm[nr] = lst[y];
        lst[y] = nr;
    }

    for(int i = 1; i <= (1 << n) - 1; i += 2)
        for(int j = 0; j <= n - 1; j++)
            d[i][j] = INF;
    d[1][0] = 0;

    for(int i = 3; i <= (1 << n) - 1; i += 2)
        for(int j = 1; j <= n - 1; j++)
        {
            d[i][j] = INF;
            if(!(i & (1 << j)))
                continue;
            for(int k = lst[j]; k; k = urm[k])
                if(i & (1 << vf[k]) && d[i - (1 << j)][vf[k]] != INF)
                    d[i][j] = minim(d[i][j], d[i - (1 << j)][vf[k]] + cost[k]);
        }

    int cminim = INF;
    for(int i = lst[0]; i; i = urm[i])
        if(d[(1 << n) - 1][vf[i]] != INF)
            cminim = minim(cminim, d[(1 << n) - 1][vf[i]] + cost[i]);

    if(lst[0] == 0 || cminim == INF)
    {
        out << "Nu exista solutie\n";
        return 0;
    }

    out << cminim << '\n';
    return 0;
}