#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int L = 20;
vector < int > E[L];
vector < vector < int > > dp(L, vector < int > ((1 << L), 1e8)), cost(L, vector < int > (L, 1e8));
int n, m, x, y, c;
int main() {
    ios_base::sync_with_stdio(false);
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        E[y].push_back(x);
        cost[x][y] = c;
    }
    dp[0][1] = 0;
    for (int mask = 0; mask < 1 << n; mask++) {
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (auto it : E[i]) {
                    if (mask & (1 << it)) {
                        dp[i][mask] = min(dp[i][mask], dp[it][mask ^ (1 << i)] + cost[it][i]);
                    }
                }
            }
        }
    }
    int ans = 2e9;
    for (auto it : E[0]) {
        ans = min(ans, dp[it][(1 << n) - 1] + cost[it][0]);
    }
    out << ans << '\n';
    return 0;
}