#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

int n, m, cost[18][18], dp[18][262144], nr, sol;
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = 0;
    for (int j = 1; j < (1<<n); j++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((j>>i) & 1)
            {
                nr = j - (1<<i);
                for (int g = 0; g < n; g++)
                {
                    if (((nr>>g) & 1) && cost[g][i] != 0)
                        dp[i][j] = min (dp[i][j], dp[g][nr] + cost[g][i]);
                }
            }
        }
    }

    sol = 0x3f;
    for (int i = 0; i < n; i++)
    {
        if (cost[i][0] != 0)
            sol = min(sol, dp[i][(1<<n)-1] + cost[i][0]);
    }
    if (sol == 0x3f) fout << "Nu exista solutie";
    else fout << sol;
    return 0;
}