#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 sol(int conf, int last)
{
    if(dp[conf][last] != 1e9)
        return  dp[conf][last];

    for(auto it = v[last].begin(); it != v[last].end(); ++it)
    {
        if(((conf >> it->first) & 1) == 1)
        {
            if (it->first == 0 && conf != (1 << (last)) + 1)
                continue;

            dp[conf][last] = min(dp[conf][last], sol(conf ^ (1 << last), it->first) + it->second);
        }
    }

    return dp[conf][last];
}
int main()
{
    cin >> n >> m;

    for(int i = 0; i <= (1 << n) - 1; ++i)
        for(int j = 1; 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(auto it = v[0].begin(); it != v[0].end(); ++it)
    {
        solution = min(solution, sol((1 << n) - 1, it->first) + it->second);
    }

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

    return 0;
}