#include <bits/stdc++.h>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int nMax = 18;
const int inf = 1e9;
int cost[nMax + 1][nMax + 1], dp[nMax + 1][(1 << nMax)];
vector <int> G[nMax + 2];
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;
        G[y].push_back(x);
    }
    int staremax = (1 << n) - 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= staremax; j++) {
            dp[i][j] = inf;
        }
    }
    dp[0][1] = 0;
    for(int stare = 0; stare <= staremax; stare++){ ///iau fiecare stare
        for(int j = 0; j < n; j++) { ///ajung in j
            if(stare & (1 << j)) { ///apartine starii
                for(const auto &i : G[j]) { ///vin din i si ma duc in j
                    if(stare & (1 << i)) { ///apartine si el starii
                        dp[j][stare] = min(dp[j][stare], dp[i][stare - (1 << j)] + cost[i][j]);
                    }
                }
            }
        }
    }
    int ans = inf;
    for(auto i : G[0]) {
        ans = min(ans, dp[i][staremax] + cost[i][0]);
    }
    if(ans == inf) {
        g<<"Nu exista solutie\n";
        return 0;
    }
    g<< ans << "\n";
    return 0;
}