#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int N, M, sol;
vector<vector<int>> cost, best;
vector<int> *G;

void dinamica() {

    int i, j;

    best[1][0] = 0;
    for(i=0; i<(1<<N); ++i)
        for(j=0; j<N; ++j)
            if(i & (1<<j))
                for(auto it=G[j].begin(), it2=G[j].end(); it!=it2; ++it)
                    if(i & (1<<*it))
                        best[i][j] = min(best[i][j], best[i^(1<<j)][*it] + cost[*it][j]);
}

int main() {

    int i, j;

    f >> N >> M;
    cost.resize(N, vector<int>(N, 1<<30));
    best.resize(1<<N, vector<int>(N, 1<<30));
    G = new vector<int>[N];
    while(M--) {
        f >> i >> j;
        G[j].push_back(i);
        f >> cost[i][j];
    }

    dinamica();

    sol = 1<<30;
    for(auto it=G[0].begin(), it2=G[0].end(); it!=it2; ++it)
        sol = min(sol, best[(1<<N)-1][*it] + cost[*it][0]);

    if(sol == 1<<30)
        g << "Nu exista solutie";
    else
        g << sol;

    f.close();
    g.close();

    return 0;
}