#include <fstream>
#include <vector>

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

int n, m, solution = 1e9, dp[262144][19];
vector <pair <int, int> > v[19];

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

    for(int i = 0; i <= (1 << n) - 1; ++i)
        for(int j = 0; j <= n; ++j)
        {
            dp[i][j] = 1e9;
        }

    dp[1][0] = 0;

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

    for (int conf = 0; conf < (1 << n); ++conf)

        for (int last = 0; last < n; ++last)
        {
            if (conf & (1 << last))
            {
                for(auto it = v[last].begin(); it != v[last].end(); ++it)
                {
                    if(((conf >> it->first) & 1) == 1)
                    {
                        dp[conf][last] = min(dp[conf][last], dp[conf ^ (1 << last)][it->first] + it->second);
                    }
                }
            }
        }

    for(auto it = v[0].begin(); it != v[0].end(); ++it)
    {
        solution = min(solution, dp[(1 << n) - 1][it->first] + it->second);
    }

    if(solution == 1e9)
        cout << "Nu exista solutie\n";
    else
        cout << solution << '\n';

    return 0;
}