#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[(1 << NMAX)][NMAX];
vector<int> G[NMAX];

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;
        G[x].push_back(y);
    }

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

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

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