#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 1000000000,
          NMAX = 18;

vector<int> adj[NMAX];
int dp[NMAX][1 << NMAX],
    cost[NMAX][NMAX];
int n, m;

inline void minSelf(int &x, int y)
{
    x = (x < y ? x : y);
}

void Init()
{
    for(int node = 0; node < n; node++)
        for(int mask = 0; mask < (1 << n); mask++)
            dp[node][mask] = INF;
}

void Read()
{
    f >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = INF;
    while(m--)
    {
        int x, y, c;
        f >> x >> y >> c;
        adj[x].push_back(y);
        cost[x][y] = c;
    }
}

void Solve()
{
    dp[0][1] = 0;
    for(int mask = 0; mask < (1 << n); mask++)
        for(int node = 0; node < n; node++)
        {
            if(!(mask & (1 << node)))
                continue;
            for(const int &next : adj[node])
            {
                if(mask & (1 << next))
                    continue;
                minSelf(dp[next][mask | (1 << next)],
                        dp[node][mask] + cost[node][next]);
            }
        }
}

void Print()
{
    int costMin = INF;
    for(int v = 0; v < n; v++)
        minSelf(costMin, dp[v][(1 << n) - 1] + cost[v][0]);
    if(costMin != INF)
        g << costMin << '\n';
    else
        g << "Nu exista solutie";
}

int main()
{
    Read();
    Init();
    Solve();
    Print();
    f.close();
    g.close();
    return 0;
}