#include <fstream>
#include <iostream>
#include <string.h>
#define NMAX 19
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int cost[NMAX][NMAX];
int dp[NMAX][(1 << (NMAX - 1))];
const int oo = 0x3f3f3f3f;
int main()
{
    memset(dp, oo, sizeof(dp));
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    dp[0][1] = 0;
    for (int mask = 1; mask < (1 << n); mask++)
    {
        for (int j = 1; j < n; j++)
        {
            if (mask & (1 << j))
            {
                int prev = mask ^ (1 << j);

                for (int k = 0; k < n; k++)
                {
                    if (prev & (1 << k) && cost[k][j])
                        dp[j][mask] = min(dp[j][mask], dp[k][prev] + cost[k][j]);
                }
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (cost[i][0])
            dp[0][(1 << n) - 1] = min(dp[0][(1 << n) - 1], dp[i][(1 << n) - 1] + cost[i][0]);
    }
    if (dp[0][(1 << n) - 1] != oo)
        fout << dp[0][(1 << n) - 1];
    else
        fout << "Nu exista solutie";
    return 0;
}