#include <bits/stdc++.h>

using namespace std;

const int NMAX = 20, inf = 0x3f3f3f3f;

int N, M;
int C[NMAX][NMAX], DP[1 << 18][NMAX];
vector<int> G[NMAX];

int Go(int mask, int last) {
    if (DP[mask][last] != -1)
        return DP[mask][last];

    DP[mask][last] = inf;
    for (const int &it: G[last])
        if (mask & (1 << it))
            DP[mask][last] = min(DP[mask][last], Go(mask ^ (1 << last), it) + C[it][last]);
    return DP[mask][last];
}

int main() {
    assert(freopen("hamilton.in", "r", stdin));
    assert(freopen("hamilton.out", "w", stdout));

    int i, j;
    int x, y, c;

    cin >> N >> M;
    while (M--) {
        cin >> x >> y >> c;
        G[y].push_back(x);
        C[x][y] = c;
    }

    memset(DP, -1, sizeof DP);
    DP[1][0] = 0;

    int answer = inf;
    for (int i = 0; i < N; ++i)
        if (C[i][0])
            answer = min(answer, Go((1 << N) - 1, i) + C[i][0]);

    cout << answer << '\n';
    return 0;
}