#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 1e9;

const int N = 18;
int dp[N + 1][(1 << N) + 1], cost[N + 1][N + 1];

vector <pair <int ,int> > gt[N + 1];

int n, m, mn = INF, x, y, c;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> c;
        cost[x][y] = c;
        gt[y].push_back({x, c});
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
        dp[i][j] = INF;
    dp[0][1] = 0;
    for (int i = 1; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            if ((1 << j) & i)
            for (auto it : gt[j])
                if ((1 << it.first) & i)
            dp[j][i] = min (dp[j][i], dp[it.first][i ^ (1 << j)] + it.second);
    for (int i = 1; i < n; ++i)
        if (cost[i][0])
        mn = min (mn, dp[i][(1 << n) - 1] + cost[i][0]);
    if (mn == INF)
        {
            cout << "Nu exista solutie";
            return 0;
        }
    cout << mn << '\n';
    return 0;
}