#include <fstream>
#include <vector>

using namespace std;

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

#define INF 100000000
#define MX 20

vector<vector<int> > G;

int C[1 << MX][MX], Cost[MX][MX];

int main() {
    int N, M;
    fin >> N >> M;

    G.resize(N + 2);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            Cost[i][j] = INF;
        }
    }

    int x, y, cost;
    for(int i = 1; i <= M; i++) {
        fin >> x >> y >> cost;

        Cost[x][y] = cost;
        G[y].push_back(x);
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            C[i][j] = INF;
        }
    }

    C[1][0] = 0;

    for(int config = 0; config < (1 << N); config++) {
        for(int j = 0; j < N; j++) {
            if((1 << j) & config) {
                for(int k = 0; k < G[j].size(); k++) {
                    if(config & (1 << G[j][k]))
                        C[config][j] = min(C[config][j],
                                             C[config ^ (1 << j)][G[j][k]] + Cost[G[j][k]][j]);
                }
            }
        }
    }

    int ans = INF;

    for(int i = 0; i < G[0].size(); i++) {
        ans = min(ans, C[(1 << N) - 1][G[0][i]] + Cost[G[0][i]][0]);
    }

    if(ans == INF) fout << "Nu exista solutie";
    else fout << ans << '\n';

    return 0;
}