#include <bits/stdc++.h>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int nMax = 18;
const int INF = 1E9;
const int stareMax = (1<<18);
int cost[nMax][nMax], dp[nMax][stareMax];
vector <int> Graf[nMax+1];
int main()
{
    int n, m, x, y, c;
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        f>> x >> y >> c;
        cost[x][y] = c;
        Graf[y].push_back(x);
    }
    int stareN = ((1 << n) - 1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= stareN; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][1] = 0;
    for(int stare = 0 ; stare <= stareN; stare++) {
        for(int j = 0; j < n; j++) {
            if(stare & (1 << j)) {
                for(auto i : Graf[j]) {
                    if(stare & (1 << i)) {
                        dp[j][stare] = min(dp[j][stare], dp[i][stare - (1 << j)] + cost[i][j]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for(auto i : Graf[0]) {
        ans = min(ans, dp[i][stareN] + cost[i][0]);
    }
    if(ans == INF) {
        g<<"Nu exista solutie\n";
        return 0;
    }
    g<< ans << "\n";
    return 0;
}