#include <fstream>
#define INF 1e9 + 2
#define NMAX 20

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

int n, m, a[NMAX][NMAX], dp[(1<<NMAX)][NMAX];

void citire();
void rezolvare();

int main()
{
    citire();
    rezolvare();
    return 0;
}

void citire()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x][y] = c;
    }
}

void rezolvare()
{
    int maxim = (1 << n);

    for (int mask = 0; mask < maxim; mask++)
        for (int j = 0; j < n; j++)
            dp[mask][j] = INF;

    dp[1][0] = 0;

    for (int mask = 1; mask < maxim; mask++)
        for (int j = 0; j < n; j++)
            if ((1 << j) & mask)
            {
                for (int k = 0; k < n; k++)
                    if (a[k][j] && ((1 << k) & mask))
                        dp[mask][j] = min(dp[mask][j], dp[mask^(1 << j)][k] + a[k][j]);
            }
    int cost = INF;
    for (int j = 0; j < n; j++)
        if (a[j][0])
            cost = min(cost, dp[maxim-1][j] + a[j][0]);
    if (cost == INF)
        fout << "Nu exista solutie";
    else
        fout << cost;
}