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

// dp[mask][i] = cel mai scurt lant care porneste din 0 care ajunge in i 
// si trece prin toate nodurile din mask

// dp[{2, 3, 5}][3] = min(dp[{2, 5}][2] + cost(2, 3), dp[{2, 5}][5] + cost(5, 3))

// min(dp[(1 << n) - 1][i] + cost(i, 0))

int dp[(1 << 18)][18];
int cost[18][18];

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] = 1e9;
        }
    }
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            dp[mask][i] = 1e9;
        }
    }

    for(int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            if(mask & (1 << i)) {
                for(int j = 0; j < n; j++) {
                    if(j != i && (mask & (1 << j))) {
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i]);
                    }
                }
            }
        }
    }
    int sol = 1e9;
    for(int i = 0; i < n; i++) {
        sol = min(sol, dp[(1 << n) - 1][i] + cost[i][0]);
    }
    if(sol != 1e9) {
        cout << sol;
    } else {
        cout << "Nu exista solutie";
    }
}