#include <bits/stdc++.h>
using namespace std;

//dp bitmask

//N <= 18

//1. O(N! * N) - generam toate permutarile si dupa verificam verificam
//fiecare permutare

//2. O(2 ^ N * (N + M))
//1. Prespunem ca ciclu incepe in nodul 0
//2. dp[i][S] = costul minim sa ajung de la 0 la i trecand prin
//nodurile din S; dp[3][{0, 1, 3, 4}]

//N = 6
//S = {0, 1, 3, 4} => 0011011

const int NMAX = 18;
const int INF = 1e9;
int dp[NMAX][1 << NMAX];
vector<int> L[NMAX];
int cost[NMAX][NMAX];

int main() {
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cost[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        L[y].push_back(x);
        cost[x][y] = c;
    }
    for(int i = 0; i < n; i++) {
        for(int S = 0; S < (1 << n); S++) {
            dp[i][S] = INF;
        }
    }
    //dp[i][S] = costul minim sa ajung de la 0 la i trecand prin
    //nodurile din S; dp[3][{0, 1, 3, 4}]
    //dp[i][S] = min(dp[i][S], dp[j][S \ {i}] + cost(j, i)), unde j
    //este un nod care poate ajunge in i
    dp[0][1] = 0; //costul minim de la 0 la 0 trecand prin nodurile din {0}
    for(int S = 1; S < (1 << n); S++) {//2^n
        for(int i = 0; i < n; i++) {//n
            if(S & (1 << i)) {
                for(auto j : L[i]) {
                    dp[i][S] = min(dp[i][S], dp[j][S ^ (1 << i)] + cost[j][i]);
                }
            }
        }
    }
    int sol = INF;
    for(int i = 0; i < n; i++) {
        sol = min(sol, dp[i][(1 << n) - 1] + cost[i][0]);
    }
    if(sol == INF) {
        cout << "Nu exista solutie";
    } else {
        cout << sol;
    }

}