#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

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

const int NMAX = 20;
const int MMAX = (1 << 18) + 5;
const int INF = 0x3f3f3f3f;

vector <int> graph[NMAX];
int n, m, minim = INF;
int cost[NMAX][NMAX];
int dp[MMAX][NMAX];

int dpMem(int config, int nod)
{
    if (dp[config][nod] == -1)
    {
        dp[config][nod] = INF;
        for (int i = 0; i < graph[nod].size(); ++i)
            if (config & (1 << graph[nod][i]))
                dp[config][nod] = min(dp[config][nod], dpMem(config - (1 << nod), graph[nod][i]) + cost[graph[nod][i]][nod]);
    }
    return dp[config][nod];
}

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

    memset(dp, -1, sizeof(dp));
}

int main()
{
    read();
    dp[1][0] = 0;
    for (int i = 1; i < n; ++i)
    {
        if (cost[i][0])
            minim = min(minim, dpMem((1 << n) - 1, i) + cost[i][0]);
    }
    if (minim != INF)
        fout << minim;
    else
        fout << "Nu exista solutie";


    return 0;
}