#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <climits>

using namespace std;

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

vector<pair<int, int>> v[20];
vector<pair<int, int>> V[20];
int dp[(1<<18)][20];
int n;

int cost(int crr) {

    dp[1][0] = 0;

    for(int i = 0; i < (1<<n); i++) {
        for(int j = 0; j < n; j++) {
            if(!(i == 1 && j == 0))
                dp[i][j] = INT_MAX/2;
            if((i&(1<<j)) != 0) {
                for(int K = 0; K < V[j].size(); K++) {
                    if((i&(1<<(V[j][K].first))) != 0) {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][ V[j][K].first ] + V[j][K].second);
                    }
                }
            }
            //if(i < 20)
            //    cout << i << " " << j << " " << dp[i][j] << '\n';
        }
    }

    int fin = 1<<n;
    fin--;
    int mi = INT_MAX/2;

    for(int i = 0; i < V[0].size(); i++) {
        mi = min(mi, dp[fin][V[0][i].first] + V[0][i].second);
    }

    return mi;

}

int main() {

    int m;
    in >> n >> m;
    int x,y,z;

    for(int i = 1; i <= m; i++) {
        in >> x >> y >> z;
        v[x].push_back({y, z});
        V[y].push_back({x, z});
    }

    int f = cost(0);

    if(f == INT_MAX/2)
        out << "Nu exista solutie";
    else
        out << cost(0);

    return 0;

}