#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int NMAX = 20;
int c[NMAX][NMAX];
vector<int> In[NMAX];
int dp[(1 << 20)][NMAX];
void hamilton()
{
    int n, m, x, y, z;

    in >> n >> m;

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            c[i][j] = 1e9;

    for (int i = 0; i < m; i++)
    {
        in >> x >> y >> z;
        In[y].push_back(x);
        c[x][y] = z;
    }

    for (int mask = 1; mask < (1 << n); mask++)
        for (int i = 0; i < n; i++)
            dp[mask][i] = 1e9;
    dp[1][0] = 0;

    for (int mask = 1; mask < (1 << n); mask++)
        for (int i = 1; i < n; i++)
            if (mask & (1 << i))
                for (int k = 0; k < In[i].size(); k++)
                {
                    int x = In[i][k];
                    dp[mask][i] = min(dp[mask][i], c[x][i] + dp[mask - (1 << i)][x]);
                }

    int res = 1e9;

    for (int i = 1; i < n; i++)
        res = min(res, dp[(1 << n) - 1][i] + c[i][0]);

    if (res == 1e9)
        out << "Nu exista solutie";
    else
        out << res;
}
int main()
{
    hamilton();
    return 0;
}