#include <bits/stdc++.h>
#define N 18
#define oo 1000000000

using namespace std;

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

int n, m;
int cost[N][N], dp[1 << N][N], ans = oo;
vector <int> L[N];

int main()
{
    fin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cost[i][j] = oo;

    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = oo;

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        cost[a][b] = c;
        L[b].push_back(a);
    }

    dp[1][0] = 0;
    for (int mask = 3; mask < (1 << n); mask += 2)
    {
        for (int i = 0; i < n; i++)
            if (mask & (1 << i))
                for (auto j : L[i])
                    if (mask & (1 << j))
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i]);
    }

    for (int i = 0; i < n; i++)
        ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    if (ans == oo)
        fout << "Nu exista solutie";
    else fout << ans;

    return 0;
}