#include <fstream>
#include <vector>

using namespace std;

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

const int nmax = 20;
const int inf = 1e9;

int n, m, res, cost[nmax][nmax], dp[(1 << nmax)][nmax];
vector <int> v[nmax];

void read(){
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
        v[y].push_back(x);
    }
}

void init(){
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = inf;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = inf;
    res = inf;
}

void solve(){
    dp[1][0] = 0;
    for(int mask = 0; mask < (1 << n); mask++)
        for(int i = 0; i < n; i++)
            if(mask & (1 << i))
                for(auto j:v[i])
                    if(mask & (1 << j))
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i]);

    for(auto j:v[0])
        res = min(res, dp[(1 << n) - 1][j] + cost[j][0]);

    if(res == inf)
        fout << "Nu exista solutie\n";
    else
        fout << res;
}

int main()
{
    fin >> n >> m;
    init();
    read();
    solve();

    return 0;
}