#include <bits/stdc++.h>
using namespace std;
using llx = long long;

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

const int inf = 1<<30;
vector<vector<int>> c;
vector<vector<int>> vt;
vector<vector<int>> dp; // dp[x][j] = costul minim al unui lant de la 0 la j, cu nodurile deja vizitate stocate in starea x

int main()
{
    int n, i, j, k, m, x, y, z, rasp;

    fin >> n >> m;
    c.assign(n, vector<int>(n, inf));
    vt.resize(n);
    dp.assign(1<<n, vector<int>(n, inf));
    for (i = 0; i<m; i++)
    {
        fin >> x >> y >> z;
        c[x][y] = z;
        vt[y].push_back(x);
    }

    dp[1][0] = 0;
    for (i = 1; i<(1<<n); i++)
        for (j = 0; j<n; j++)
            if (i & (1<<j))
                for (const auto &nprec : vt[j])
                    if (i & (1<<nprec))
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][nprec] + c[nprec][j]);
    
    rasp = inf;
    for (const auto &nprec : vt[0])
        rasp = min(rasp, dp[(1<<n)-1][nprec] + c[nprec][0]);
    
    if (rasp == inf)
        fout << "Nu exista solutie";
    else
        fout << rasp;
    return 0;
}