#include <fstream>
#include <vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m, i, j, ans, x, y, cost[20][20], dp[262150][20];
const int INF = 1e9;
vector<int> A[20];
int main()
{
    in >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cost[i][j] = INF; //init matricea de costuri cu infinit
    for (i = 0; i < m; i++)
    {
        in >> x >> y;
        A[y].push_back(x); //inversam, practic mergem de la ultimul nod la primul
        in >> cost[x][y];
    }
    for (i = 0; i < (1<<n); i++)
        for (j = 0; j < n; j++)
            dp[i][j] = INF; //init DP-ul
    dp[1][0] = 0; //cazul de baza
    for (i = 0; i < (1<<n); i++)
        for (j = 0; j < n; j++)
        {
            if ((i&(1<<j)) == 0) //nu exista nodul acesta in matrice
                continue;
            for (auto ind : A[j])
            {
                if ((i & (1<<ind)) == 0)
                    continue;
                dp[i][j] = min(dp[i][j], dp[i^(1<<j)][ind] + cost[ind][j]); //recurenta e ciudata, practic cream nodul de la ind la j pentru fiecare j care apare in masca
            }
        }
    ans = INF;
    for (auto ind : A[0])
        ans = min(ans, dp[(1<<n)-1][ind]+cost[ind][0]); //solutia se afla cand masca e doar 11111...1
    if (ans == INF)
        out << "Nu exista solutie";
    else
        out << ans;
    return 0;
}