#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 19, MMAX = 18*17 + 2, inf = 19000001;
int n, m, cost[NMAX][NMAX], dp[(1<<NMAX)+2][NMAX], mn = inf;

void citire()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for (int st = 0; st < (1<<n); st++)
        for (int i = 0; i < n; i++)
            dp[st][i] = inf;
}

int main()
{
    citire();

    dp[1][0] = 0;
    for (int st = 1; st < (1<<n); st++)
    {
        for (int i = 0; i < n; i++)
        {
            if(((1<<i) & st) > 0 && dp[st][i] != inf)
            {
                for (int j = 0; j < n; j++)
                {
                    if((!((1<<j) & st)) && cost[i][j])
                        dp[st+(1<<j)][j] = min(dp[st+(1<<j)][j], dp[st][i] + cost[i][j]);
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (dp[(1<<n)-1][i] != inf && cost[i][0])
            mn = min(mn, dp[(1<<n)-1][i] + cost[i][0]);
    }
    if (mn == inf)
        fout << "Nu exista solutie";
    else
        fout << mn;

    return 0;
}