#include <fstream>
#include <vector>

using namespace std;

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

int n, m, x, y, c, r=2e9;
int cost[20][20], dp[1<<18+1][20];
vector <int> v[20];

int main()
{
    fin >> n >> m;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            cost[i][j] = 1e9;
    for(int i=1; i<=m; i++){
        fin >> x >> y >> c;
        v[y].push_back(x);
        cost[x][y] = c;
    }
    for(int i=0; i<=1<<n; i++)
        for(int j=0; j<=n; j++)
            dp[i][j] = 2e9;
    dp[1][0] = 0;
    for(int mask=3; mask<(1<<n); mask+=2)
        for(int i=1; i<n; i++)
            if(mask & (1<<i)){
                int submask = mask^(1<<i);
                for(int j=0; j<v[i].size(); j++)
                    dp[mask][i] = min(dp[mask][i], dp[submask][v[i][j]] + cost[v[i][j]][i]);
            }
    for(int i=1; i<n; i++)
        r = min(r, dp[(1<<n)-1][i]+cost[i][0]);
    if(r >= 2e9)
        fout <<"Nu exista solutie";
    else
        fout << r;
    return 0;
}

//2166782