#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 18;
const int MASKMAX = (1 << 18);
const int inf = 1e9;

int n,m;
int mat[NMAX][NMAX];
int dp[NMAX][MASKMAX];


int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        mat[x][y] = c;
    }
    if (n == 1)
    {
        out << 0;
        return 0;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            dp[i][j] = inf;
    dp[0][1] = 0;
    for (int mask = 1; mask < (1 << n); mask++)
    {
        for (int nod = 1; nod < n; nod++)
        {
            if ((mask & (1 << nod)) == 0)
                continue;
            int dmin = inf;
            for (int i = 0; i < n; i++)
                if ((mask & (1 << i)) != 0 and i != nod and mat[i][nod] != 0)
                    dmin = min(dmin,dp[i][mask - (1 << nod)] + mat[i][nod]);
            dp[nod][mask] = dmin;
        }
    }
    int cmin = inf;
    for (int i = 1; i < n; i++)
        if (dp[i][(1 << n) - 1] != inf and mat[i][0] != 0)
            cmin = min(cmin,dp[i][(1 << n) - 1] + mat[i][0]);
    if (cmin == inf)
        out << "Nu exista solutie";
    else
        out << cmin;
    return 0;
}