#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 < n; ++i)
            if (i != nod && (config & (1 << i)) && cost[i][nod])
                dp[config][nod] = min(dp[config][nod], dpMem(config - (1 << nod), i) + cost[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[x].push_back(y);
        cost[x][y] = c;
    }

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

int main()
{
    read();
    dp[1][0] = 0;
    for (int i = 1; i < n; ++i)
    {
        vector<int>::iterator it = find(graph[i].begin(), graph[i].end(), 0);
        if (it != graph[i].end())
            minim = min(minim, dpMem((1 << n) - 1, i) + cost[i][0]);
    }
    if (minim != INF)
        fout << minim;
    else
        fout << "Nu exista solutie";


    return 0;
}