#include <bits/stdc++.h>

using namespace std;

#define ST_DIO 0
#if ST_DIO
    #define fin cin
    #define fout cout
#else
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
#endif  // ST_DIO

const int INF = 2e9 + 7;
vector<pair<int, int>> gr[19];
int n, m, i, j, cost[19][19];
int d[(1 << 18) + 2][19];

int main() {
    if(ST_DIO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) cost[i][j] = INF;
    }

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

        x++;
        y++;

        fin >> cost[x][y];

        gr[y].push_back({x, cost[x][y]});
    }

    for(i = 0; i < (1 << n); i++) {
        for(j = 1; j <= n; j++) d[i][j] = INF;
    }

    d[1][1] = 0;
    for(i = 2; i < (1 << n); i++) {
        for(j = 1; j <= n; j++) {
            if(!(i >> (j - 1) & 1)) continue;

            for(auto [u, c] : gr[j]) {
                if(d[i - (1 << (j - 1))][u] != INF) {
                    d[i][j] = min(d[i][j], d[i - (1 << (j - 1))][u] + c);
                }
            }
        }
    }

    int rasp = INF;
    for(i = 2; i <= n; i++) {
        if(cost[i][1] != INF) rasp = min(rasp, d[(1 << n) - 1][i] + cost[i][1]);
    }

    if(rasp != INF) fout << rasp;
    else fout << "Nu exista solutie";

    return 0;
}