#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>

using namespace std;

#define NMAX 18
#define MMAX 262144
#define PMAX 524288
#define LOG 17
#define INF 0x3f3f3f3f
#define BS 127
#define MOD 1000000007

#define ll long long
#define ull unsigned long long
#define ldb long double

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, x, y, c, ans = INF;
vector<int> gr[NMAX + 2];
int dp[MMAX + 2][NMAX + 2], cost[NMAX + 2][NMAX + 2];

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cost[i][j] = INF;
        }
    }

    while (m--) {
        fin >> x >> y >> c;
        gr[x].push_back(y);
        cost[x][y] = c;
    }

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INF;
        }
    }

    dp[1][0] = 0;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                for (auto it : gr[j]) {
                    if (!(i & (1 << it))) {
                        dp[i | (1 << it)][it] = min(dp[i | (1 << it)][it], dp[i][j] + cost[j][it]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    }

    fout << ans;
    return 0;
}