#include <bits/stdc++.h>

using namespace std;
ifstream r("hamilton.in");
ofstream w("hamilton.out");
vector<vector<int>>g;
int n, m;
int cost[20][20], d[262150][20];
int main()
{
    r>>n>>m;
    memset(cost, 1e9, sizeof cost);
    for(int i = 1; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            d[i][j] = 1e9;
        }
    }
    g.resize(m + 5);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        r>>x>>y>>cost[x][y];
        g[y].push_back(x);
    }
    d[1][0] = 0;
    for(int i = 1; i < (1 << n); i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))
            {
                for(int k = 0; k < g[j].size(); k++){
                    if(i & (1 << g[j][k])){
                        d[i][j] = min(d[i][j], d[i ^ (1 << j)][g[j][k]] + cost[g[j][k]][j]);
                    }
                }
            }
        }
    }
    int sol = 1e9;
    for(int i = 0; i < g[0].size();i++){
		sol = min(sol, d[(1<<n) - 1][g[0][i]] + cost[g[0][i]][0]);
    }
    if(sol==1e9){
        w<<"Nu exista solutie\n";
    }
    else{
        w<<sol<<"\n";
    }
    return 0;
}