#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;
const int NMAX(19);
int mat[NMAX][NMAX], dp[NMAX][(1 << 19)];

int main()
{
    int n, m;
    fin >> n >> m;

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

    for(int i = 0; i < n; ++i)
        for(int msk = 0; msk <= (1 << n); ++msk)
            dp[i][msk] = 1e9;

    dp[0][1] = 0;
    for(int msk = 1; msk < (1 << n); ++msk)
    {
        for(int i = 0; i < n; ++i)
            if((1 << i) & msk)
                for(int j = 0; j < n; ++j)
                    if(mat[i][j] && !((1 << j) & msk))
                        dp[j][msk | (1 << j)] = min(dp[j][msk | (1 << j)], dp[i][msk] + mat[i][j]);
    }

    int minn = 1e9;
    for(int i = 1; i < n; ++i)
        if(mat[i][0] && dp[i][(1 << n) - 1] != 1e9)
            minn = min(minn, dp[i][(1 << n) - 1] + mat[i][0]);

    if(minn != 1e9)
        fout << minn<< '\n';
    else fout << "Nu exista solutie\n";
    return 0;
}