#include <fstream>
#include <climits>

using namespace std;

const int INF = 1e9;

int n, m, cost[20][20], dp[20][1 << 20];
// dp[i][mask] = costul minim de la 0 la i prin drumul mask

void Hamilton()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
        {
            dp[i][j] = INF;
        }
    }
    dp[0][1] = 0;
}

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> n >> m;
    int x, y, c;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cost[i][j] = INF;
        }
    }
    while (m--)
    {
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    Hamilton();
    for (int mask = 0; mask < (1 << n); mask++)
    {
        for (int i = 0; i < n; i++)
        {
            if (mask & (1 << i))
            {
                for (int j = 0; j < n; j++)
                {
                    if (mask & (1 << j))
                    {
                        dp[i][mask] = min(dp[i][mask],
                                          dp[j][mask ^ (1 << i)] + cost[j][i]);
                    }
                }
            }
        }
    }
    int sol = INF;
    for (int i = 0; i < n; i++)
    {
        if (cost[i][0])
        {
            sol = min(sol, dp[i][(1 << n) - 1] + cost[i][0]);
        }
    }
    if (sol == INF)
    {
        fout << "Nu exista solutie";
    }
    else
    {
        fout << sol;
    }
    return 0;
}