#include <bits/stdc++.h>

using namespace std;

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

int n, m;

int main()
{
    in >> n >> m;
    vector <vector<int>> inn(n), ad(n, vector<int>(n, 1e9));
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        in >> x >> y >> z;
        inn[y].push_back(x);
        ad[x][y] = z;
    }
    vector <vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;
    for(int mask = 3; mask < (1 << n); mask += 2)
    {
        for(int i = 1; i < n; i++)
        {
            if(mask & (1 << i))
            {
                for(int j:inn[i])
                {
                    dp[mask][i] = min(dp[mask][i], dp[mask - (1 << i)][j] + ad[j][i]);
                }
            }
        }
    }
    int sol = 1e9;
    for(int i = 1; i < n; i++)
        sol = min(sol, dp[(1 << n) - 1][i] + ad[i][0]);
     if (sol == 1e9)
        out << "Nu exista solutie\n";
    else
        out << sol << '\n';
    return 0;
}