#include <bits/stdc++.h>

using namespace std;

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

int dp[262144][20], cost[20][20];
vector <vector <int>> adjL;
int i, sol, n, m, j, nr1, nr2, nr3;

int bkt(int conf, int last){
    if (dp[conf][last] == -1){
        dp[conf][last] = 1000000000;
        for (int i = 0; i < adjL[last].size(); ++i){
            if (conf & (1 << adjL[last][i])){
                if (adjL[last][i] == 0 && conf != (1 << last) + 1)
                    continue;
                dp[conf][last] = min(dp[conf][last], bkt(conf ^ (1 << last), adjL[last][i]) + cost[adjL[last][i]][last]);
            }
        }
    }
    return dp[conf][last];
}


int main()
{
    fin >> n >> m;
    adjL.assign(n, vector <int>());
    for (i =0; i < n; ++i)
        for(j = 0; j < n; ++j)
            cost[i][j] = 1000000000;
    for (i = 0; i < m; ++i){
        fin >> nr1 >> nr2 >> nr3;
        cost[nr1][nr2] = nr3;
        adjL[nr2].push_back(nr1);
    }
    sol = 1000000000;
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;
    for (i = 0; i < adjL[0].size(); ++i)
        sol = min (sol, bkt((1<<n)-1, adjL[0][i]) + cost[adjL[0][i]][0]);
    if (sol == 1000000000) fout << "Nu exista solutie\n";
    else fout << sol << '\n';

    return 0;
}