#include <fstream>
#include <vector>
#define NMAX 18

using namespace std;

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

const int INF = 1e9 + 5;

struct ok{
    int vecin, cost;
};

vector <ok> adj[NMAX];
int dp[NMAX + 1][1 << NMAX];

int main()
{
    int n, m, i, j, a, b, c, mask;
    in >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        in >> a >> b >> c;
        adj[b].push_back({a, c});
    }

    for (i = 0; i < NMAX; ++i)
    {
        for (j = 0; j < (1 << NMAX); ++j)
            dp[i][j] = INF;
    }

    dp[0][1] = 0;
    for (mask = 2; mask <= (1 << n) - 1; ++mask)
    {
        for (i = 0; i < n; ++i)
        {
            int x = (mask & (1 << i));
            if (x)
            {
                for (j = 0; j < adj[i].size(); ++j)
                {
                    int vecin = adj[i][j].vecin;
                    int cost = adj[i][j].cost;
                    int y = (mask & (1 << vecin));
                    if (y)
                        dp[i][mask] = min(dp[i][mask], dp[vecin][(mask - (1 << i))] + cost);
                }
            }
        }
    }

    int minn = INF;
    for (i = 0; i < adj[0].size(); ++i)
    {
        int vecin = adj[0][i].vecin;
        int cost = adj[0][i].cost;
        minn = min(minn, dp[vecin][(1 << n) - 1] + cost);
    }

    if (minn != INF)
        out << minn;
    else
        out << "Nu exista solutie";
    return 0;
}